完全图染色（困难版）：题解

思路

对整个顶点集应用条件，可知红图与蓝图中恰有一个不连通。固定不连通的颜色，把它的一个连通块取为含顶点 $1$ 的规范块；块内与剩余顶点的染色仍需满足同样条件，由此得到递归分解。

令 $A_n$ 表示固定外层颜色方向后、连同两个单色退化结构的计数。基值为 $A_1=1,A_2=2$。组合块大小并选择其余标号顶点，可得到指数型生成函数卷积递推。

做法

预处理阶乘与逆阶乘，定义

$$C_i=\frac{A_i}{i!},\qquad D_i=\frac{A_i/2}{(i-1)!},$$

其中两个基值按递归边界单独设定。则

$$A_n=2(n-1)!\sum_{i=1}^{n-1}C_iD_{n-i}.$$

最终答案为 $A_n-2$，减去全红和全蓝两个不合法方案。

二次 DP

直接枚举卷积下标即可在 $O(n^2)$ 时间计算所有 $A_i$，足以处理 $n\le3000$。

分块卷积

困难版按约 $1200$ 个新系数为一块。每到块边界，用 NTT 重新计算当前 $C*D$；块内新加入而尚未进入卷积的左右两段直接枚举补上。每个位置的零散枚举不超过块长，NTT 次数约为 $n/B$。

取模数 $998244353$，其原根为 $3$，可直接进行二进制长度 NTT。

复杂度

分块大小记为 $B$。时间复杂度为 $O(nB+\frac nB\,n\log n)$，取 $B\approx\sqrt{n\log n}$；空间复杂度为 $O(n)$。

子任务算法

• $n\le6$：枚举 $2^{\binom n2}$ 种边染色，对所有顶点子集分别检查红、蓝连通性。
• $n\le3000$：使用二次卷积递推。
• 无限制：使用 NTT 分块卷积。