》》》点我查看「视频」详解》》》

[GESP202412 八级] 排队

题目描述

小杨所在班级共有 $n$ 位同学，依次以 $1,2,\dots ,n$ 标号。这 $n$ 位同学想排成一行队伍，其中有些同学之间关系非常好，在队伍里需要排在相邻的位置。具体来说，有 $m$ 对这样的关系（$m$ 是一个非负整数）。当 $m\ge 1$ 时，第 $i$ 对关系（$1\le i\le m$）给出 $a_i,b_i$，表示排队时编号为 $a_i$ 的同学需要排在编号为 $b_i$ 的同学前面，并且两人在队伍中相邻。

现在小杨想知道总共有多少种排队方式。由于答案可能很大，你只需要求出答案对 $10^9+7$ 取模的结果。

输入格式

第一行，两个整数 $n,m$，分别表示同学们的数量与关系数量。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示一对关系。

输出格式

一行，一个整数，表示答案对 $10^9+7$ 取模的结果。

样例 #1

样例输入 #1

4 2
1 3
2 4

样例输出 #1

2

样例 #2

样例输入 #2

3 0

样例输出 #2

6

样例 #3

样例输入 #3

3 2
1 2
2 1

样例输出 #3

0

提示

对于 $20\%$ 的测试数据点，保证 $1\le n\le 8$，$0\le m\le 10$。

对于另外 $20\%$ 的测试数据点，保证 $1\le n\le 10^3$，$0\le m\le 1$。

对于所有测试数据点，保证 $1\le n\le 2\times 10^5$，$0\le m\le 2\times 10^5$。

解题思路

当 $m=0$ 时，即求解 $n$ 个同学排队的方案数：$A_n^n$，即 $n!$。

当 $m=1$ 时，我们可以使用捆绑法，将两个同学打包，变为一个同学，那么方案数为 $(n-1)!$。

那么本题转换为，将有特殊需求的同学进行捆绑之后，剩余的同学数量。

那么如何对每一条关系做处理？假设 $a$ 要在 $b$ 前面，那么我们可以使用两个数组进行标记，$r_a=b$，$l_b=a$，表示 $a$ 的右边是 $b$，$b$ 的左边是 $a$。当出现 $a$ 在多个人前面，或者是 $b$ 在多个人后面，则直接输出 $0$。

接下来我们考虑如何处理成环的情况，如样例三所示，$1$ 要在 $2$ 前面，且 $2$ 要在 $1$ 前面，可以成功通过我们上述处理。考虑用并查集维护每一个特殊处理的区间，当 $a$ 与 $b$ 为同一个区间时，则直接输出 $0$。

另外本题特别坑的地方在于，某条建议可能重复出现，如下样例：

2 2
1 2
1 2

那么我们可以进行特判出现过的情况，若 $r_a=b$ 且 $l_b=a$，则表示一出现过该关系，即 continue。

最后，如何判断一个是一个小团体，还是一个人呢？

可以用并查集，若当前点的祖先为自己，则算做一个人，这样一个团体仅会被算一次。

AC_Code

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 2e5 + 10, MOD = 1e9 + 7;typedef long long LL;int n, m;
int p[N];
int l[N], r[N];int find(int x)
{if (x != p[x])p[x] = find(p[x]);return p[x];
}int main()
{cin >> n >> m;for (int i = 1; i <= n; ++ i )p[i] = i;while (m -- ){int a, b;cin >> a >> b;if (r[a] == b && l[b] == a)continue;if (r[a] || l[b] || find(a) == find(b)){cout << 0 << endl;return 0;}r[a] = b, l[b] = a;a = find(a), b = find(b);p[a] = b;}int res = 1, k = 1;for (int i = 1; i <= n; ++ i )if (find(i) == i)res = (LL)res * k ++ % MOD;cout << res << endl;return 0;
}

》》》点我查看「视频」详解》》》