Loading... [题目传送门](https://codeforces.com/gym/105949/problem/E) ## 0x00 引理 ### 引理 1 对竞赛图缩点后形成的 DAG 形如一条链。 **证明**：归纳法证明。 - **基例**：对于 $ n = 1 $ 或 $ 2 $ 阶竞赛图，结论显然成立（缩点后为单点或一条有向边）。 - **归纳假设**：假设对任意 $ k \leq n-1 $ 阶竞赛图，缩点后的 DAG 是一条链。 - **归纳步骤**：新增一个顶点 $ v $ 到 $ n-1 $ 阶竞赛图中，考察其与现有 SCC 的连接关系： 1. **若存在某个 SCC $ U_i $**，使得 $ v $ 与 $ U_i $ 之间既有 $ v \to U_i $ 的边，又有 $ U_i \to v $ 的边，则 $ v $ 必须并入 $ U_i $（否则会破坏链结构）。 2. **否则**，对所有 SCC $ U_i $，$ v $ 与 $ U_i $ 之间的边方向一致（全入或全出）。此时： - 由竞赛图性质，存在唯一分界点 $ j $，使得对所有 $ i < j $ 有 $ U_i \to v $，对所有 $ i \geq j $ 有 $ v \to U_i $。 - 将 $ v $ 作为新 SCC 插入链中位置 $ j $，仍保持链结构。 - 综上，归纳成立。 ### 引理 2 一个 $ n \geq 4 $ 阶强连通竞赛图一定存在一个 $ n-1 $ 阶子强连通竞赛图。 **证明**：考虑归纳法。对于任意一个 $ n-1 $ 阶竞赛图 $ G $，如果其添加一个点 $ z $ 之后变成了一个强连通竞赛图，那么： 1. 对 $ G $ 进行强连通分量的缩点之后，按拓扑序排好，形成的 SCC 为 $ U_1, U_2, \dots, U_m $。 - 若 $ m = 1 $，结论显然成立。 - 若 $ m \geq 2 $，此时因为新图是强连通图，所以存在 $ x \in U_1 $ 和 $ y \in U_m $，满足 $ (y, z), (z, x) \in E $。由于 $ n \geq 4 $，删除其他任意一个点后，$ x $、$ y $、$ z $ 未被删除。这样既不会影响其所在 SCC 内部的强连通性，也不会影响整体的强连通性。 ### 引理 3 强连通 $ n \geq 3 $ 阶竞赛图存在一条哈密顿回路。 **证明**（归纳法）： 1. **基例**（$ n = 3 $）： - 强连通竞赛图必为有向三元环，显然存在哈密顿回路。 2. **归纳假设**： - 假设对任意 $ k \leq n-1 $ 阶强连通竞赛图，均存在哈密顿回路。 3. **归纳步骤**（构造 $ n $ 阶竞赛图的回路）： - 设 $ T $ 为 $ n $ 阶强连通竞赛图，删除任意顶点 $ v_n $ 得 $ n-1 $ 阶子图 $ T' $。 - **情况1**：若 $ T' $ 强连通，由归纳假设存在哈密顿回路 $ C = (v_1 \to v_2 \to \dots \to v_{n-1} \to v_1) $。 - 若存在 $ i $ 使得 $ v_i \to v_n $ 且 $ v_n \to v_{i+1} $，则将 $ v_n $ 插入 $ C $ 得到新回路 $ (v_1 \to \dots \to v_i \to v_n \to v_{i+1} \to \dots \to v_1) $。 - **否则**，若所有边 $ v_i \to v_n $ 或所有边 $ v_n \to v_i $，则 $ T $ 不强连通（矛盾），故情况1必然成立。 - **情况2**：若 $ T' $ 非强连通，其缩点后为链 $ U_1 \to U_2 \to \dots \to U_m $（由引理1）。 - 因 $ T $ 强连通，$ v_n $ 必须同时有边指向 $ U_1 $ 和来自 $ U_m $ 的边（否则链无法闭合）。 - 对每个 $ U_i $ 内部取哈密顿回路（归纳假设），并通过 $ v_n $ 连接相邻 SCC，构造全局回路。 ## 0x01 $\mathcal{O}(n\log^2n)$ 做法 容易发现只需要计数存在一个大于等于 $k$ 强连通分量的竞赛图个数，于是转化成全部小于等于 $k$。首先计算一个大小为 $k$ 的强连通竞赛图个数，使用容斥，用全部方案减去有多个的方案，每次枚举缩点后最后一个连通块，那么有： $$ \begin{align} f_n=&2^{n\choose 2}-\sum_{i=1}^{n-1}{n\choose i}2^{n-i\choose 2}f_i\\ =&2^{n\choose 2}-n!\sum_{i=1}^{n-1}\frac{2^{n-i\choose 2}}{(n-i)!}\frac{f_i}{i!} \end{align} $$ 于是分离出了 $n-i,i$，分治 NTT 可以做到 $\mathcal{O}(n\log^2n)$。 然后用 EGF 把这个东西拼出来，令 $F(x)$ 为其 EGF，那么答案的 EGF 就是 $A(x)=(1-F(x))^{-1}$。 此处题解做法结束了。 ## 0x02 $\mathcal{O}(n\log n)$ 做法 但是这个做法太蠢了，你继续推一下啊，观察一下全是阶乘。我们直接令 $f_n=\frac{f_n}{n!},g_n=\frac{2^{n\choose 2}}{n!}$，也就是其 EGF 的系数，推一下： $$ \begin{align} f_n=&\frac{2^{n\choose 2}}{n!}-\sum_{i=1}^{n-1}\frac{2^{n-i\choose 2}}{(n-i)!}f_i\\ =&g_n-\sum_{i=1}^{n-1}g_{n-i}f_i \end{align} $$ 令我们发现 $g$ 的系数里面有负数，那么直接令 $g'_n=-g_n,f'_n=-f_n,f'_0=1$，那么有： $$ \begin{align} f'_n=&\sum_{i=1}^{n}g'_{n-i}f'_i \end{align} $$ 牛逼的来了，那不就是[P4721 【模板】分治 FFT - 洛谷](https://www.luogu.com.cn/problem/P4721)的形式吗，令 $G'(x)$ 为 $g'$ 的生成函数，这个我们知道就是等于： $$ F'(x)=\frac{1}{1-G'(x)} $$ 然后 $$ A(x)=\frac{1}{1-(-F'(x))} $$ 然后更牛逼的来了，你发现只需要求出，$G(x)$，然后正好正负号全部抵消完，加一也全部不用管，而且转 EGF 都省略了： $$ \begin{align} G(x)=&\sum_{i=0}^{k} \frac{2^{i\choose 2}}{i!}x^i\\ P(x)=&G^{-1}(x)\bmod{x^{k+1}}\\ A(x)=&P^{-1}(x) \end{align} $$ 注意两次求逆不能抵消，应为长度不一样。 放下部分代码，省略 NTT 板子： ```cpp u32 f[100010],ifac[100010],pw[100010]; int main(){ u32 factn=1; int i,j; int n=read(); int k=read(); if(k==2) return puts("0"),0; for(pw[0]=i=1;i<=n;++i) factn=(u64)factn*i%NTTp; ifac[n]=POL::invNum(factn); for(i=n;i;--i) ifac[i-1]=(u64)ifac[i]*i%NTTp; for(i=0;i<=n;++i) pw[i]=(u64)POL::qpow(2,u64(i)*(i-1)/2%(NTTp-1))*ifac[i]%NTTp; Poly F;F.push_back(1); f[0]=1; for(i=1;i<k;++i) F.push_back(pw[i]); F=F.inv(); F.resize(n+1); F=F.inv(); print(u64(pw[n]+NTTp-F[n])*factn%NTTp); return 0; } ``` 最后修改：2025 年 06 月 10 日 © 允许规范转载 赞 如果觉得我的文章对你有用，使用点这里使用虚拟货币进行赞赏