[AGC046F] Forbidden Tournament

吐槽

想了好久,猜了个结论,只会一个 \(\mathcal O(n^4)\) 做法复杂度降不下去了,去看了眼题解结果拖到最后直接看到一个 \(\mathcal O(n^4)\)。。。。

\(\mathcal O(n^4)\)\(200\),这不 atcoder。。。

做法

先不考虑度数,分析合法竞赛图的性质。(这里假定阅读本文的人对竞赛图强连通分量的性质有所了解)

引理 1 如果一个竞赛图不存在三元环,那么它一定是一个 DAG。

证明 如果存在边 \((u,v), (v,w)\),那么一定存在边 \((u,w)\)。假设存在一个环,考虑环上的一条边 \((u,v)\)。由于 \(v\) 可以走到 \(u\),所以存在边 \((v,u)\),这与竞赛图的定义矛盾。

引理 2 如果一个竞赛图是合法的,那它所有出度不为 \(0\) 的强连通分量大小都为 \(1\)

证明 如果有一个出度不为 \(0\) 的强连通分量大小不为 \(1\),根据 引理 1,这个强连通分量存在一个三元环。任取一个这个强连通分量出发可以到达的点,这四个点就构成了题目中定义的不允许出现的子图。

有了引理 \(2\),我们可以枚举有多少个出度不为 \(0\) 的强连通分量,如果恰有 \(x\) 个,剩下的一个强连通分量最大入度就不能超过 \(K-x\),只需对 \(n-x\) 个点入度不超过 \(K-x\) 的强连通合法竞赛图计数即可。

接下来我们把重点放在分析强连通合法竞赛图的性质上。

\(in(u)\) 是所有从 \(v\) 出发有一条指向 \(u\) 的边的点 \(v\) 的集合,\(out(u)\) 是所有从 \(u\) 出发有一条指向 \(v\) 的边的点 \(v\) 的集合。

引理 3 如果一个强连通竞赛图是合法的,那么对于它的任何一个点 \(u\)\(in(u)\) 的导出子图构成一个无环竞赛图。

证明 如果 \(in(u)\) 的导出子图中有环,根据 引理 1\(in(u)\) 中存在一个三元环,与 \(u\) 构成一个合法的图中不允许出现的子图,推出了矛盾。

对于一个长为 \(n\) 的整数序列 \(a\)\(1 \le a_i < n-1\),定义它对应的有向图 \(G = (V, E)\):对于任意一对点 \(u \neq v\)\((u,v)\in E\) 当且仅当 \((v - u + n) \bmod n \le a_u\)\((v-u+n) \bmod n > a_v\)。注意这样的 \(G\) 可能不是一个竞赛图。如果 \(a\) 对应的图 \(G\) 是竞赛图,我们就称 \(a\) 是合法的。

引理 4 一个 \(n\) 个点的强连通竞赛图合法的充要条件是它同构与某个长度为 \(n\) 的合法整数序列 \(a\) 对应的竞赛图。

充分性的证明

对于一个合法的整数序列 \(a\),设它对应的竞赛图为 \(G = (V,E)\)。显然,\((1,2), (2,3), \ldots, (n, 1) \in E\)。这些边构成了一个 \(G\) 的哈密顿回路,同时这也说明 \(G\) 是强连通的。设这个哈密顿回路对应的子图为 \(C\)。我们认为 \(1,2,\ldots,n\)\(C\) 上按顺时针排列。

假设存在不同的四个点 \(a,b,c,d \in V\),使得 \((a,d),(b,d),(c,d) \in E\),且 \(a,b,c\) 构成三元环 (这时 \(a,b,c\) 内的边的方向可能有两种)。用 \(a,b,c\) 把环 \(C\) 划分为三段。不妨假 \(a,b, c\)\(C\) 上按顺时针方向排列,点 \(d\) 在以 \(a,c\) 为端点的段中,即 \(a,b,c,d\) 在环上按顺时针方向排列。

如果 \((a,b),(b,c),(c,a) \in E\)\((c-a+n)\bmod n < (d-a+n) \bmod n\),而 \((c,a) \in E, (a,d) \in E\),与整数序列 \(a\) 对应的竞赛图的定义矛盾。

否则 \((b,a),(c,b),(a,c) \in E\)\((a-c+n)\bmod n < (b-c+n) \bmod n\),而 \((a,c) \in E, (c,b) \in E\),与整数序列 \(a\) 对应的竞赛图的定义矛盾。

所以 \(G\) 是一个合法的强连通竞赛图。

必要性的证明

考虑按点数归纳。当点数为 \(3\) 时结论显然成立。假设所有点数小于 \(n\) 的强连通合法竞赛图都与某个合法整数序列 \(a\) 对应的竞赛图同构。现在我们来证明所有点数等于 \(n\) 的强连通合法竞赛图 \(G\) 都与某个合法整数序列 \(a\) 对应的竞赛图同构。

\(f(u)\) 表示 \(in(u)\) 的导出子图中,出度为 \(0\) 的点 (这样的点存在且唯一)。考虑有向图 \(P\)\(u\)\(v\) 有一条边当且仅定 \(v = f(u)\)

显然 \(P\) 是一个基环内向树森林。如果 \(P\) 中存在一个不包含所有点的环 \(S\),那么在 \(G\)\(S\) 的导出子图 \(H\) 是一个大小小于 \(n\) 的强连通合法竞赛图,根据归纳假设,\(H\) 与某个合法序列对应的竞赛图同构。

由于 \(G\) 是强连通图,所以一定存在点 \(u\)\(u \notin S\),且 \(u\)\(S\) 中的某个点 \(v\)\(G\) 中有一条边。假设 \(H\) 与某个合法序列对应的竞赛图 \(A\) 同构,根据 \(f\) 的定义和序列对应的竞赛图的定义,把环 \(S\) 中的边方向反过来,得到的环一定对应于 \(A\)\(1,2,\ldots,n\) 构成的哈密顿回路。所以对与 \(H\) 中每个点 \(x\)\(in(x)\) 都是环 \(S\) 上从 \(x\) 开始连续的一段。\(u \in in(v)\),假设 \(u\)\(in(v)\) 导出子图中拓扑序第 \(k\) 大的点,那么 \(f^k(v) = u\) (这里 \(f^k\) 表示复合 \(k\) 次),与 \(u\) 不在环上矛盾。所以 \(P\) 是一个包含所有点的环。

显然,如果 \(v \in in(u)\)\(f(u) \neq v\),则 \(v \in in(f(u))\)。由于 \(P\) 构成的环中每个点出现了一次,因为 \(G\) 强连通,也不可能存在一个点 \(u\) 到所有点在 \(G\) 中都有边。所以,对于每个 \(u\)\(out(u)\) 一定都是 \(P\) 构成的环上连续一段,且以 \(f^{-1}(u)\) 结尾。这就证明了 \(G\) 也同构与某个合法整数序列 \(a\) 对应的竞赛图。

这样我们就把问题转化为了对合法的序列 \(a\) 计数,然后乘上 \((n-1)!\) 即可。

不难发现,\(a\) 合法的充要条件为:

  • \(1 \le a_i < n - 1\)
  • \(a_{i \bmod n + 1} \ge a_i - 1\)
  • \(\forall 2 \le i \le a_1 + 1, i + a_i \le n, \forall j \in (i-1 + a_{i-1}, i + a_i], a_j = i-1+n-j\)

枚举 \(a_1\),然后 DP 决定前 \(a_1 + 1\) 项即可,度数限制容易在 DP 的过程中处理。

这个 DP 是 \(\mathcal O(n^2)\) 的,除了要枚举 \(a_1\) 之外,还要枚举这个强连通竞赛图的点数。所以总复杂度为 \(\mathcal O(n^4)\)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>

using namespace std;

const int maxn = 210;

int fac[maxn], ifac[maxn], dp[maxn][maxn], sum[maxn][maxn];
int n, K, mod, ans;

int qpow(int x, int y) {
int ret = 1;
while (y) {
if (y & 1) ret = 1LL * ret * x % mod;
x = 1LL * x * x % mod;
y >>= 1;
}
return ret;
}

int binom(int x, int y) {
if (y > x) return 0;
return 1LL * fac[x] * ifac[x-y] % mod * ifac[y] % mod;
}

int main() {
scanf("%d%d%d", &n, &K, &mod);
fac[0] = 1; for (int i = 1; i <= n; i++) fac[i] = 1LL * fac[i-1] * i % mod;
for (int i = 0; i <= n; i++) ifac[i] = qpow(fac[i], mod-2);
for (int T = 0; T <= K; T++) {
// max in-deg <= K-T
// |V| = n - T
int res = 0, c = n - T;
if (c == 1) {
res = 1;
} else {
if (K - T <= 0) continue;
// min out-deg >= (c-1)-(K-T)
int m = max(1, c - 1 - (K - T));
for (int s = m; s <= c - 2; s++) {
for (int i = 1; i <= c - 1; i++) dp[1][i] = 0;
dp[1][s] = 1;
for (int i = 1; i <= c - 1; i++) sum[1][i] = (sum[1][i-1] + dp[1][i]) % mod;
for (int i = 2; i <= s + 1; i++) {
for (int j = 0; j <= c - 1; j++) dp[i][j] = 0;
for (int j = m; j <= (c - 1 - m); j++) {
dp[i][j] = sum[i-1][j+1];
}
for (int j = 1; j <= c - 1; j++) sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
}
int add = sum[s + 1][c - s - 1];
res = (res + add) % mod;
}
}
res = 1LL * res * fac[c - 1] % mod * binom(n, T) % mod * fac[T] % mod;
ans = (ans + res) % mod;
}
printf("%d\n", ans);
return 0;
}