Sky Full of Stars
题目链接:
题目大意:
给定一个 \(n \times n\) 的矩形,在里面填充三种颜色,求使得至少一行或至少一列同色的方案数。
解法
容斥
我们不去考虑反演,直接开始容斥,我们不难将问题进行转化,去计算此时答案的补集,那么最后的答案就是 \(3^{n\times n} -\) 补集。我们在将问题进行转化,我们不如去直接计算第一行同色且且二行同色 \(\cdots\) 且第一列同色且第二列同色 \(\cdots\) 的方案数,我们令 \(F\) 为满足上面条件的方案数,那么最后的答案就是 :
\]
我们考虑如何去计算 \(F\)。我们不难发现对于 \(i,j>0\),\(\left(i=0\right) \lor (j=0)\),\((i=0) \land (j=0)\)是三种不同的情况,那么我们分开计算。
首先对于 \((i=0) \land (j=0)\),此时没有任何限制条件,对应的 \(F(S) = 3^{n\times n}\)。
对于 \((i=0) \lor (j=0)\),此时对于发现行列之间没有交叉点,也就是行列之间没有颜色的约束,故此时的 \(F(S) = 2\times \sum_{i=1}^n (-1)^i \binom{n}{i} 3^{n^2 -ni +i}\)。
对于这个式子,我们考虑如何去掉求和符号就行优化,我们准备直接利用二项式定理去进行优化:
F(S) &= 2\times \sum_{i=1}^n (-1)^i \binom{n}{i} 3^{n^2 -ni +i}\\
&=2\times 3^{n^2} \times \sum_{i=1}^n (-1)^i \binom{n}{i} 3^{-ni+i} \\
&=2\times 3^{n^2} \times \sum_{i=1}^n \binom{n}{i} (-3^{(1-n)})^i \\
&=2\times 3^{n^2} \times [(1-3^{(1-n)})^n -1]
\end{aligned}\]
最后考虑 \(i,j>0\) 的情况我们不难发现此时对应的 \(i\) 行,\(j\) 列的颜色应该相同,所以对应的 \(F(S) = \sum_{i=1}^n \sum_{j=1}^n (-1)^{i+j} \binom{n}{i} \binom{n}{j} 3^{n^2 - n(i+j)-ij + 1}\)
之后和第二种情况一样,大力推式子,二项式定理优化即可。
反演
我们首先明确两个含义:
\(F_{i,j}\) 表示至少 \(i\) 行 \(j\) 列同色的方案数
\(G_{i,j}\) 表示恰好 \(i\) 行,\(j\) 列同色的方案数。
那么我们就知道最后答案为 \(Ans = F_{0,0} - G_{0,0}\) 即全集减去没有一行并且没有一列同色的方案数。
那么根据二维二项式反演可知 :
\]
由此可知:
G_{0,0} &= \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} (-1)^{i+j} \binom{i}{0} \binom{j}{0} F_{i,j} \\&
= \sum_{i=0}^{\infty} \sum_{j=0}^{\infty} (-1)^{i+j} F_{i,j}
\end{aligned}\]
对于 \(F_{i,j}\) 的计算方法上面已经提到过了,这里就不再提了。
最后贴一下代码吧
Code
#include<bits/stdc++.h>
#define int long long
#define ll long long
const int M = 1e6 + 7 , mod = 998244353;
int fac[M] , inv[M];
inline int Pow(int a , int b) {
int ans = 1; for(; b; b >>= 1 , a = a * a % mod) if(b & 1) ans = ans * a % mod;
return ans;
}
inline int C(int n , int m) {return fac[n] * inv[m] % mod * inv[n - m] % mod;}
signed main () {
int n; std::cin >> n;
inv[0] = fac[0] = 1;for(int i = 1; i <= 1e6; ++ i) fac[i] = fac[i - 1] * i % mod , inv[i] = Pow(fac[i] , mod - 2);
int ans = 0;
for(int i = 1; i <= n; ++ i) {
int tmp = C(n , i) * Pow(3 , (mod - 1 - i * n % (mod - 1))) % mod * (Pow(1 - Pow(3 , i - n + mod - 1) + mod , n) - 1) % mod ;
if(i & 1) ((ans -= tmp) += mod) %= mod;
else (ans += tmp) %= mod;
}
ans = -ans * Pow(3 , (n * n + 1) % (mod - 1)) % mod;
((ans -= 2ll * Pow(3,(ll)n * n % (mod - 1)) % mod * (Pow(1 - Pow(3,mod - n) + mod,n) - 1) % mod) += mod) %= mod;
std::cout << (ans + mod) % mod<< '\n';
return 0;
}
最后感谢 slongle 大佬的指导
最新文章
- 4 django系列之HTML通过form标签来同时提交表单内容与上传文件
- windows7 64,32位下scrapy爬虫框架的环境搭建
- CentOS 6 安装 python 2.7 和 mod_wsgi 运行pyocr[tesseract]
- linux下获取帮助
- 《JS高程》事件类型学习笔记
- HDU 5881 Tea
- (Java)《head first java》值得Java或面向对象基础的新手看。
- ProcessStartInfo.UseShellExecute 属性
- Window vagrant 安装部署【转】
- Audio-支持多个音频文件格式
- Oracle数据导入导出imp/exp(转)
- 17.java.lang.CloneNotSupportedException
- ubuntu下安装memcached与php扩展测试使用
- Golang之Context的使用
- springboot~application.properties和application.yml的使用
- VC调用静态库、动态库
- linux目录说明
- 绑定hover事件
- 非root用户在80端口运行nginx
- 自学工业控制网络之路1.4-典型的现场总线介绍CAN