codeforces 997C

未分类

---

Question:
一个$n*n(1\leq n \leq 10^6)$的网格，给每个格子染上红蓝黄三种颜色之一，问有多少种染色方案能使染色后的网格至少存在一行或一列的颜色相同。

Solution:
考虑容斥：

$$ans=\sum_{i=0}^n\sum_{j=0}^n[i+j>0]C_n^iC_n^jf(i,j)g(i,j)$$
这里$f(i,j)$表示容斥的系数，$g(i,j)$表示有$i$行和$j$列颜色分别一样.
先考虑$f(i,j)$的计算，这里直接上结论：
$$f(i,j)=(-1)^{i+j+1}$$
证明：
显然容斥的系数只和$i+j$有关.
一个结论：$\sum_{i=0}^n[i\%2=0]C_n^i=\sum_{i=0}^n[i\%2=1]C_n^i=2^{n-1}$，在$n>0$时成立.
下面用数学归纳法证明：
如果$i+j=1$，显然$f(i+j)=1$成立.
如果$i+j=2$，显然$f(i+j)=-1$成立.
当$i+j=k(k\geq 2)$时：
如果$k$是奇数：
$$C_k^1-C_k^2+C_k^3-...-C_k^{k-1}+f(i,j)C_k^k=1$$
转换一下：
$$2^{k-1}-1-(2^{k-1}-1)+f(i,j)C_k^k=1$$
显然有$f(i,j)=1.$
如果$k$是偶数：
$$C_k^1-C_k^2+C_k^3-...+C_k^{k-1}+f(i,j)C_k^k=1$$
转换一下：
$$2^{k-1}-(2^{k-1}-2)+f(i,j)=1$$
显然有$f(i,j)=-1.$
综上得证$f(i,j)=(-1)^{i+j+1}$.

下面考虑$g(i,j)$的计算：
如果$i=0$或$j=0$时，假设$i=0$：

$$g(0,j)=3^j3^{n*(n-j)}$$
否则：
$$g(i,j)=3*3^{(n-i)*(n-j)}$$

那么$i=0$或$j=0$的情况对答案的贡献是：

$$ans_1=2*\sum_{i=1}^nC_n^i(-1)^{i+1}3^j3^{n*(n-j)}$$
这个预处理阶乘和逆元之后直接用快速幂算即可.
$i>0,j>0$的情况对答案的贡献是:
$$\begin{align*} ans_2&=\sum_{i=1}^n\sum_{j=1}^nC_n^iC_n^j(-1)^{i+j+1}3*3^{(n-i)(n-j)} \\ &=3\sum_{i=1}^nC_n^i(-1)^{i+1}\sum_{j=1}^nC_n^j(-1)^j(3^{n-i})^{n-j} \\ &=3\sum_{i=1}^nC_n^i(-1)^{i+1}\left(\sum_{j=0}^nC_n^j(-1)^j(3^{n-i})^{n-j}-3^{n*(n-i)}\right) \\ &=3\sum_{i=1}^nC_n^i(-1)^{i+1}\left((-1+3^{n-i})^n-3^{n*(n-i)}\right) \\ \end{align*}$$
最后一步转换由二项式定理$(a+b)^n=\sum_{i=0}^nC_n^ia^ib^{n-i}$得来.
$$ans=ans_1+ans_2$$
总时间复杂度$O(nlogn).$

题目链接:http://codeforces.com/contest/997/problem/C
参考代码:http://codeforces.com/contest/997/submission/39856715