SCCPC2025 E - Competition Graph 竞赛图单log题解

Zi_Gao · 2025-06-10 22:02:35 · 题解

题目传送门

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 之后变成了一个强连通竞赛图，那么：

对 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 阶竞赛图存在一条哈密顿回路。

证明（归纳法）：

基例（ n = 3 ）：
- 强连通竞赛图必为有向三元环，显然存在哈密顿回路。
归纳假设：
- 假设对任意 k \leq n-1 阶强连通竞赛图，均存在哈密顿回路。
归纳步骤（构造 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 - 洛谷的形式吗，令 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 板子：

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;
}

SCCPC2025 E - Competition Graph 竞赛图 单log题解