CF997C
Sky Full of Stars
定义 $f(a,b)$ 表示钦定 $a$ 行 $b$ 列颜色相同的方案数。
我们发现 $a,b$ 是否非零对答案是有影响的，不妨分开讨论。
若 $a,b\ne 0$，则：
$$f(a,b)=3 \binom{n}{a} \binom{n}{b} 3 ^ {(n-a)(n-b)}$$
因为行与列有交点，导致被钦定的行和列颜色必定相同，所以先确定这个颜色，再取确定哪 $a$ 行哪 $b$ 列，然后再随意确定剩余格子的涂色。
若 $ab=0,a+b\ne 0$，此时我们只有行的颜色相同，或只有列的颜色相同，不妨以行的颜色相同考虑，即 $a\ne 0$，则：
$$f(a,0)=\binom{n}{a}3^{a}3^{n(n-a)}$$
对于 $ b \ne 0$ 的情况是同理的。
若 $a=b=0$，则我们所有的格子都是任意涂色的：
$$f(0,0)=3 ^ {n ^ 2}$$
接下来我们令 $g(a,b)$ 表示恰好有 $a$ 行 $b$ 列颜色相同的方案数，根据组合意义：
$$f(a,b)= \sum _ {i = a} ^ {n} \sum _ {j = b} ^ { n } \binom{i}{a} \binom{j}{b} g(i,j) $$
然后我们考虑二项式反演：
$$g(a,b)= \sum _ {i=a} ^ {n} \sum _ {j=b} ^ {n} (-1) ^ {i-a} \binom{i}{a} (-1) ^ {j-b} \binom{j}{b} f(i,j)$$
介于我们最后的答案是：
$$Ans = 3 ^ {n^2} - g(0,0)$$
只要计算 $g(0,0)$ 就好了：
$$g(0,0) = \sum _ {i=0} ^ {n} \sum _ {j=0} ^ {n} (-1) ^ {i+j} f(i,j)$$
我们有了 $O(n^2)$ 的计算方法，但显然还需要优化。
考虑化简式子。
因为我们的 $f$ 是分类讨论得到的，为了方便化简，仍然分类讨论：
若 $a,b\ne 0$，则：
$$
\begin{aligned}
& \sum _ {i=1} ^ {n} \sum _ {j=1} ^ {n} (-1) ^ {i+j} 3 \binom{n}{i} \binom{n}{j} 3 ^ {(n-i)(n-j)}
\\
=& 3 ^ {n ^ 2 + 1} \sum _ {i=1} ^ {n} \binom{n}{i} (-1) ^ {i} 3 ^ {-in}
\sum _ {j=1} ^ {n} \binom{n}{j} (-1) ^ {j} 3 ^ {-jn} 3 ^ {ij}
\\
=& 3 ^ {n ^ 2 + 1} \sum _ {i=1} ^ {n} \binom{n}{i} (-1) ^ {i} 3 ^ {-in}
\sum _ {j=1} ^ {n} \binom{n}{j} (-1) ^ {j} 3 ^ {j(i-n)}
\\
=& 3 ^ {n ^ 2 + 1} \sum _ {i=1} ^ {n} \binom{n}{i} (-1) ^ {i} 3 ^ {-in}
\sum _ {j=1} ^ {n} \binom{n}{j} 1 ^ {n-j} ( - 3 ^ {i-n}) ^ j
\\
=& 3 ^ {n ^ 2 + 1} \sum _ {i=1} ^ {n} \binom{n}{i} (-1) ^ {i} 3 ^ {-in}
((1 - 3 ^ {i-n} ) ^ n-1)
\end{aligned}
$$于是这一部分快速幂可以 $O(n\log n)$ 计算了。
若 $ab=0,a+b\ne 0$，因为两维的情况相同，我们只要算出某一维的贡献然后翻倍即可。
$$
2 \sum _ {i=1} ^ {n} (-1) ^ {i} \binom{n}{i} 3 ^ {i} 3 ^ {n(n-i)}
$$快速幂暴力上就完了，时间复杂度 $O(n\log n)$。
若 $a=b=0$，这一部分贡献就是 $3 ^ {n ^ 2}$。
介于我们的答案就是 $3 ^ {n ^ 2} - g (0 , 0)$，这一部分就被抵消了。
所以最后我们的答案就是上面算出的两部分之和的相反数。
最后总的时间复杂度是 $O(n\log n)$ 的。
代码：
1 |
|