题目详情题解（0）讨论（0）提交记录（0）

AT_abc217_f.[ABC217F] Make Pair

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

一共 2N2N 个学生站成一排，其中有 MM 对朋友关系。老师每次从队列中挑出两个相邻的学生作为同桌。为了关系和睦，每次选出的两个学生必须是朋友关系。选出的两个学生离开队列，空出来的位置左右合拢。

请问老师有多少种方式选完所有学生？对于两种选人的方案，即使同桌关系相同，只要离开队列的顺序不同，也算是不同的方案。

输入格式

先输入一行两个整数 NN、MM，然后输入 MM 行数据，每行两个数 AiA_i 和 BiB_i，表示两个同学的朋友关系。

输出格式

一个数，为所得方案数对 998244353998244353 取模后得到的值。

输入输出样例

  • 输入#1

    2 3
1 2
1 4
2 3

    输出#1

    1

  • 输入#2

    2 2
1 2
3 4

    输出#2

    2

  • 输入#3

    2 2
1 3
2 4

    输出#3

    0

说明/提示

  • 1≤N≤2001 \leq N \leq 200
  • 0≤M≤N(2N−1)0 \leq M \leq N(2N-1)
  • 1≤Ai<Bi≤2N1 \leq A_i < B_i \leq 2N
  • 所有 (Ai,Bi)(A_i, B_i) 是不同的。
  • 输入全部为整数。

输入解题思路，AI测评打分。不知道怎么写?

首页