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

题目传送门

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 - 洛谷的形式吗，令 $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;
}