基础知识

容斥原理

左转这篇文章~

二项式反演

已知 $f(x)$ 表示恰好使用 $x$ 个不同元素形成特定结构的方案数，$g(x)$ 表示从 $x$ 个元素中选出 $i\ge0$ 个元素形成特定结构的方案数。显然有：

若已知 $f(x)$ ，则：

通过 $g(x)$ 求 $f(x)$ 的过程就被称为二项式反演。

题单链接 ZR 2026 Summer C 7.31

Sky Full of Stars (CodeForces-997C/洛谷-CF997C)

我们设 $f(i,j)$ 表示至少 $i$ 行 $j$ 列颜色相同的方案数，根据容斥原理，总方案数：

考虑 $i=0$ 的情况，容易发现，染色的每列共有 $3$ 种选择，则总共 $3^j$ 种选择，未染色列每个格子都有 $3$ 种选择，共有 $3^{n(n-j)}$ 种情况。总计 $3^{n^2-nj+j}$ 种情况。$j=0$ 同理。

考虑 $ij\ne0$ 的情况，发现所有染色行列因为互相制约，只有 $3$ 种可能。其余未染色格子各有 $3$ 种选择，共有 $3^{(n-i)(n-j)}$ 种可能，总计 $3^{n^2-ni-nj+1}$ 种可能。

我们拆出 $ij=0$ 的情况，总共：

那么 $ij\ne0$ 的情况总共：

种可能。拆项整理，提公因式，得到：

变形：

注意到二项式定理：

所以代入 $a=-3^{-n+i}\ ,\ b=1$，得到：

发现原式从 $1$ 开始枚举，所以我们减去一个 $1$ 代回原式得到：

预处理 $C_n^i\ , 3^i\ ,3^{ni}$ 可以做到常数较小的 $O(n\log_2n)$ ，注意取模和逆元。