"a 紧挨在 b 前面"会把两人焊成一条链;冲突或成环答案 0,否则答案 = 块数阶乘。
小杨所在班级共有 n 位同学,依次以 1, 2, …, n 标号。这 n 位同学想排成一行队伍,其中有些同学之间关系非常好,在队伍里需要排在相邻的位置。具体来说,有 m 对这样的关系(m 是一个非负整数)。当 m ≥ 1 时,第 i 对关系(1 ≤ i ≤ m)给出 aᵢ, bᵢ,表示排队时编号为 aᵢ 的同学需要排在编号为 bᵢ 的同学前面,并且两人在队伍中相邻。
现在小杨想知道总共有多少种排队方式。由于答案可能很大,你只需要求出答案对 10⁹ + 7 取模的结果。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 4 2 |
| 输出 #1 | 2 |
| 输入 #2 | 3 0 |
| 输出 #2 | 6 |
| 输入 #3 | 3 2 |
| 输出 #3 | 0 |
a 排在 b 前面而且两人相邻"意味着 a、b 之间不能插任何人,顺序也不能反。a 和 b 就像被焊在了一起:一旦 1 → 3,队伍里就必然出现连续的一小段 …1, 3…。4 2 / 1 3 / 2 4 就串成 [1, 3] 和 [2, 4] 两块。k 个块时答案就是 k!(样例 1:2! = 2)。0:① 冲突——某人被要求有两个不同的后继(或两个不同的前驱);② 成环——像样例 3 的 1 → 2 → 1,两人互为首尾,谁也排不进去。相邻约束链合并前驱 / 后继唯一性冲突判定判环阶乘取模
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m;随后 m 行 aᵢ, bᵢ |
| 输出 | 一行一个整数:方案数对 10⁹ + 7 取模 |
| 数据范围 | 1 ≤ n ≤ 2 × 10⁵,0 ≤ m ≤ 2 × 10⁵ |
| 关系含义 | a 必须排在 b 前面,并且两人相邻 |
| 部分分 | 20%:n ≤ 8, m ≤ 10;20%:n ≤ 10³, m ≤ 1 |
| 特例 | m = 0 时答案就是 n! |
a 后面紧跟 b,b 后面又紧跟 c……每一步都锁死了相邻关系,于是这一串人只能整体出现,相当于把若干人打包成一个不可拆的块1 → 2 → 1;④ 自环 a = a(自己排在自己前面还相邻)k 个块作为整体排成一行的方式有 k × (k − 1) × … × 1 = k! 种,由乘法原理直接得到答案把每条约束翻译成 nxt / pre 两个数组:
| 约束 | 含义 | nxt 变化 | pre 变化 |
|---|---|---|---|
| 1 3 | 1 后面紧跟 3 | nxt[1] = 3 | pre[3] = 1 |
| 2 4 | 2 后面紧跟 4 | nxt[2] = 4 | pre[4] = 2 |
块头 = 前面没有任何人的同学
pre[1] = 0 → 1 是块头
pre[2] = 0 → 2 是块头
pre[3] = 1、pre[4] = 2,都不是块头
块头有 2 个:1 和 2
从 1 出发:1 → nxt[1] = 3 → nxt[3] = 0(停)
从 2 出发:2 → nxt[2] = 4 → nxt[4] = 0(停)
两条链:1 → 3(2 人)、2 → 4(2 人)
覆盖数 = 2 + 2 = 4
✅ 覆盖数 4 = n,没有环
块数 k = 块头个数 = 2
两块分别是 [1, 3] 和 [2, 4]
两种排法:1,3,2,4 与 2,4,1,3
k! = 2! = 2
✅ 答案 2
| 块 | 成员 | 块内顺序 | 块能换位吗 |
|---|---|---|---|
| A | [1, 3] | 固定:1 必须在 3 前面且相邻 | 能,整体搬 |
| B | [2, 4] | 固定:2 必须在 4 前面且相邻 | 能,整体搬 |
k!。3 0 正好是这个模型的极端情况:每人都自成一个块,k = 3,答案 3! = 6。下面这张表把"无解"的四种情形一次讲清。
| 输入 | 为什么无解 | 答案 |
|---|---|---|
3 2 / 1 2 / 1 3 | 同学 1 被要求有两个不同的后继(2 和 3) | 0 |
3 2 / 2 3 / 1 3 | 同学 3 被要求有两个不同的前驱(2 和 1) | 0 |
3 2 / 1 2 / 2 1 | 两人互为首尾成环,没有块头(样例 3) | 0 |
2 1 / 1 1 | 自环:1 要排在自己前面还相邻 | 0 |
constraint1:nxt[1] = 2、pre[2] = 1
constraint2:nxt[2] = 1、pre[1] = 2
两个数组都不冲突(每人恰好一个前驱、一个后继)
但 pre[1] = 2 ≠ 0,pre[2] = 1 ≠ 0
→ 一个块头也没有,覆盖数 = 0
✅ 覆盖数 0 ≠ n = 3,答案 0
nxt:1→2、2→3、3→1
pre:pre[1]=3、pre[2]=1、pre[3]=2
同样没有任何 pre = 0 的点
从块头出发一个人也走不到
✅ 覆盖数 0 ≠ 3,答案 0
k = 0 个块,若天真地输出 0! = 1 就错了。nxt 走下去,覆盖到的点数必须恰好等于 n。覆盖数不足 n,说明剩下的人全被锁在环里,答案只能是 0。1 2)不算冲突,答案照常计算。读数时就地判冲突,之后从每个块头顺 nxt 走到底,统计块数与覆盖数
把每对 (a, b) union 起来,最后数连通块个数 k
| 方案 | 复杂度 | 结论 |
|---|---|---|
| nxt / pre 顺链走一遍 | O(n + m) | ✅ 推荐,判环最直接 |
| 并查集 + 独立冲突判定 | O((n + m) α) | ✅ 可行,细节略多 |
| 枚举所有 n! 种排列 | O(n! × m) | ❌ n ≤ 2 × 10⁵,不可行 |
第一行输入 n m,随后 m 行输入一对约束 a b(a 紧挨在 b 前面)。程序会展示每条约束的处理、焊成的块、冲突 / 环的判定与最终答案。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; int n, m; int nxt[200005]; // nxt[a] = b 表示 a 后面必须紧挨着 b int pre[200005]; // pre[b] = a 表示 b 前面必须是 a bool vis[200005]; int main() { scanf("%d %d", &n, &m); bool ok = true; for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); // 冲突一:同一个人被要求有两个不同的后继 / 前驱 if (nxt[a] != 0 && nxt[a] != b) ok = false; if (pre[b] != 0 && pre[b] != a) ok = false; // 冲突二:自环(自己排在自己前面还相邻) if (a == b) ok = false; nxt[a] = b; pre[b] = a; } if (!ok) { puts("0"); return 0; } // 从每个"没有前驱"的块头顺着 nxt 一路走到底 int blocks = 0, covered = 0; for (int i = 1; i <= n; i++) { if (pre[i] != 0) continue; // 有前驱 ⇒ 不是块头 blocks++; // 发现一个新块 int u = i; while (u != 0 && !vis[u]) { // vis 防止在环里打转 vis[u] = true; covered++; u = nxt[u]; } } // 有环 ⇒ 环上的点永远走不到 ⇒ covered < n if (covered != n) { puts("0"); return 0; } // 块内顺序唯一,k 个块整体任意换位 ⇒ 方案数 = k! ll ans = 1; for (int i = 2; i <= blocks; i++) ans = ans * i % MOD; printf("%lld\n", ans); return 0; }
blocks,每一步都取模,防止溢出。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
if (nxt[a] != 0 && nxt[a] != b) ok = false; | 判冲突(后继) | 一个人只能有一个"必须紧跟自己的人";注意 nxt[a] == b 时说明是重复约束,不算冲突 |
if (pre[b] != 0 && pre[b] != a) ok = false; | 判冲突(前驱) | 对称地,一个人也只能有一个"必须紧挨在自己前面的人" |
if (pre[i] != 0) continue; | 找块头 | 前面没人的同学,一定是某条链的开头 |
while (u != 0 && !vis[u]) | 顺链走 | 沿着 nxt 走到底,同时用 vis 防死循环 |
if (covered != n) { puts("0"); return 0; } | 判环 | 走不满 n 个人 ⇒ 有人被锁在环里 ⇒ 无解 |
ans = ans * i % MOD; | 算 k! | 块整体任意排列,乘法原理 + 边乘边取模 |
return却没把剩下的输入读完——本题一次性读完整个输入,所以要么像本代码那样"读完再判",要么在循环里继续 scanf;② 把重复的同一条约束当成冲突(1 2 出现两次应当算一致);③ 只数块头、不做覆盖校验(样例 3 会被算成 0! = 1);④ 阶乘没取模或从 1 乘到 k 时漏乘;⑤ 数组越界——aᵢ, bᵢ 最大都是 n ≤ 2 × 10⁵,数组要开到 200005。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 2 | 2 | 题面样例 1:两个块,2! = 2 |
3 0 | 6 | 题面样例 2:没有约束,3! = 6 |
3 2 | 0 | 题面样例 3:成环,没有块头,答案 0 |
3 2 | 0 | 冲突:同学 1 被要求有两个不同的后继 |
3 2 | 0 | 冲突:同学 3 被要求有两个不同的前驱 |
5 3 | 2 | 焊成一块 [1,2,3,4] 加一个孤立点 5,块数 2,2! = 2 |
2 1 | 0 | 自环:自己排在自己前面还相邻,无解 |
2 2 | 1 | 重复的同一条约束不算冲突,块数 1,1! = 1 |
1 0 | 1 | n = 1 无约束:只有 1 种排法 |
8 4 | 24 | 4 个块:4! = 24 |
1 → 2 → 1)块头个数是 0,输出 0! = 1 就错了;必须校验覆盖数是否等于 n。a b 出现多次含义完全一样,不能判 0。return 又用逐行读入,残留数据会影响后续判断。k! 是天量数字,必须边乘边取模。aᵢ, bᵢ 可达 n 的上限 2 × 10⁵。nxt 走链:每个点恰好被访问一次,合计 O(n)两个长度 n + 1 的整型数组 nxt、pre,一个 vis 标记数组,都是 O(n);不需要存下所有约束,边读边处理。
✅ 线性复杂度就能解决,核心不是算得慢不慢,而是把"相邻且有序"翻译成链、再把无解的两类情形彻底堵住。
// 「相邻约束 → 链 → 块排列」通用骨架 int nxt[N], pre[N]; // 后继 / 前驱(0 表示没有) bool vis[N]; // 1) 读约束时判冲突:一个人只能有一个后继、一个前驱 if (nxt[a] && nxt[a] != b) ok = false; // a 被要求跟两个人 if (pre[b] && pre[b] != a) ok = false; // b 被要求跟两个人 if (a == b) ok = false; // 自环 nxt[a] = b; pre[b] = a; // 2) 找块头(pre == 0),顺后继走一遍 // 块数 = 块头个数;覆盖数 = n 才合法(否则有环) for (int i = 1; i <= n; i++) { if (pre[i]) continue; blocks++; for (int u = i; u && !vis[u]; u = nxt[u]) { vis[u] = true; covered++; } } if (covered != n) return puts("0"), 0; // 3) 块内顺序唯一 ⇒ 只有块之间能换位 ⇒ 答案 = blocks! ll ans = 1; for (int i = 2; i <= blocks; i++) ans = ans * i % MOD; // 经验:这类"把元素按约束打包成不可拆单元"的题 // · 先想清楚"单元内部还有没有自由度" // · 再想清楚"单元之间怎么排列" // · 最后单独处理"约束互相矛盾"的无解情形
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 约束翻译成数组 | nxt[a] = b、pre[b] = a 两个数组刻画"紧挨" | 任何"相邻 + 有序"的排列约束题 |
| 就地判冲突 | 读数时检查后继 / 前驱是否已被占用 | 输入里带"互斥要求"的题(如每人只能匹配一个) |
| 顺链走一遍判环 | 走不满 n 个点 ⇒ 有环 | 由"函数式图"(每个点出度 ≤ 1)判环的标准手法 |
| 打包成块 + 阶乘 | 块内唯一、块间任意 → k! | 排列计数题里"固定段 + 自由段"的拆解思路 |
| 边乘边取模 | 阶乘对 10⁹+7 取模 | 所有计数取模题的基本功 |
a 必须排在 b 前面(不要求相邻)",答案还这么好算吗?(提示:这时候 a、b 不再被焊死,就变成了偏序计数问题——一般的偏序计数是困难的,但若每条链还是"直链"结构,可以用树形 DP / 组合数合并。回看本题,正是"相邻"这个额外条件把问题压缩成了简单的 k!。)