题解 CF997C 【Sky Full of Stars】
command_block
·
·
题解
题意：有一个 n\times n 的正方形网格，用三种颜色染。
求有多少种方案使得至少一行或一列是同一种颜色。
答案对 998244353 取模，n\leq 10^6，时限 \texttt{4s}。
upd 2025.2.27：重新排版。
令：
答案：3^{n^2}-G(0,0)。
由组合意义易得
F(x,y)=\sum\limits_{i=x}^n\sum\limits_{j=y}^n\dbinom{i}{x}\dbinom{j}{y}G(i,j)
两个维度独立，施加高维二项式反演（两个维度的反演系数简单相乘）
\begin{aligned}
G(x,y)
&=\sum\limits_{i=x}^n\sum\limits_{j=y}^n(-1)^{i+j-x-y}\dbinom{i}{x}\dbinom{j}{y}F(i,j)\\
G(0,0)
&=\sum\limits_{i=0}^n\sum\limits_{j=0}^n(-1)^{i+j}F(i,j)
\end{aligned}
这和容斥的结论一致。
接下来考虑如何快速计算 F(i,j)，需要分类讨论。
-
$$
F(i,j)=\dbinom{n}{i}\dbinom{n}{j}\cdot 3\cdot 3^{(n-i)(n-j)}
$$
即：选定行列 x 钦定颜色 x 其余自由部分
-
$$
F(i,0)=\dbinom{n}{i}\cdot3^i\cdot3^{n(n-i)}
$$
即：选定行 x 钦定颜色 x 其余自由部分
（$i=0$ 同理）
-
回忆：
G(0,0)=\sum_{i=0}^n\sum_{j=0}^n(-1)^{i+j}F(i,j)
根据上述讨论，分三部分求和。
\begin{aligned}
S_1
&=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}F(i,j)\\
&=\sum_{i=1}^n\sum_{j=1}^n(-1)^{i+j}\dbinom{n}{i}\dbinom{n}{j}3^{(n-i)(n-j)+1}\\
&=3^{n^2+1}\sum_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\,\boxed{\sum_{j=1}^n\dbinom{n}{j}(-1)^{j}3^{j(i-n)}}\\
&=3^{n^2+1}\sum_{i=1}^n\dbinom{n}{i}(-1)^i3^{-in}\left((1-3^{i-n})^n-1\right)
\end{aligned}
快速幂就可以 O(n\log n) 计算了。
$$
\begin{aligned}
S_2&=2\sum_{i=1}^n(-1)^{i}\dbinom{n}{i}^{i+n(n-i)}\\
&=2\cdot3^{n^2}\,\boxed{\sum_{i=1}^n\dbinom{n}{i}(-1)^{i}3^{i(1-n)}}\\
&=2\cdot3^{n^2}\left((1-3^{1-n})^n-1\right)\\
\end{aligned}
$$
- **第三部分**：两个参数均为 $0$。$S_3=3^{n^2}$。
最终 $G(0,0)=S_1+S_2+S_3$。
总复杂度 $O(n\log n)$。