【计数】 CF997C 【Sky Full of Stars】
skydogli
2021-01-20 10:33:58
这题好像直接做就好了？
如果单独考虑行的情况，大概大部分人都能用简单的容斥乱杀。当然，也可以钦定第 $i$ 行为第一次满足条件的行（也就是之前的行都不合法），这个东西求和的式子是：
$$\sum_{i=1}^n (3^{n}-3)^{i-1}\times 3\times {(3^n)}^{n-i}$$
前面式子是每行都有3种满足条件的情况不能选，然后这一行红绿蓝3种合法情况，后面随意。
而现在加入了列，我们只需要强制没有任何一行满足条件，再统计列的方案即可，这样就能保证不重不漏了。于是我们只要简单地限制一下行，用容斥做的话非常方便。
枚举 $i$ 列满足条件：
$$\sum_{i=1}^n (-1)^{i-1}\binom{n}{i}f_i$$
其中 $f_i$ 表示钦定前 $i$ 列满足条件的方案数，需要考虑这 $i$ 列是否都是同一颜色。
不同的贡献：
$$(3^i-3)\times {(3^{n-i})}^{n}$$
前面是选列的方案数后面是其他列可以任意选的方案数。
全部相同的贡献：
$$3\times (3^{n-i}-1)^n$$
枚举红绿蓝，然后每一列都不能全都是这个颜色。
$f_i$ 就是两个加起来了。
这题比较简单，就顺便讲讲这个容斥的正确性。
考虑任意一种有 $m$ 列符合条件的情况，他会在 $i=1$ 时统计 $\binom{m}{1}$ 次，在 $i=2$ 时统计 $\binom{m}{2}$ 次...在 $i=k$ 时统计 $\binom{m}{k}$ 次。（注意这个统计次数和上面的式子没有关系）
所以总的贡献是：
$$\sum_{i=1}^m \binom{m}{i}(-1)^{i-1}$$
$$=-\sum_{i=1}^m \binom{m}{i}(-1)^{i}$$
$\binom{n}{0}(-1)^0$恒为 $1$，我们补进去。
$$=-(-1+\sum_{i=0}^m \binom{m}{i}(-1)^{i})$$
后面的式子等于 $(1-1)^m$ （二项式定理）
考虑$0^0=1,0^i=0(i\neq0)$。
所以右边的式子在 $m\neq 0$ 时都是0。
于是我们发现每个合法情况的贡献都是 $1$ 。
那么我们就可以心安理得地切掉这题了。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Mod 998244353
int read(){
int a=0,fh=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')fh=-1;c=getchar();}
while('0'<=c&&c<='9'){
a=a*10+c-48;
c=getchar();
}
return a*fh;
}
int ksm(int a,int x){
int ans=1,w=a;
while(x){
if(x&1)ans=ans*w%Mod;
w=w*w%Mod;
x>>=1;
}
return ans;
}
#define MN 1000005
#define pii pair<int,int>
#define mp make_pair
#define x first
#define y second
int n;
int pw[MN],fac[MN],dfac[MN],inv[MN];
int C(int m,int n){
if(m<n)return 0;
return fac[m]*dfac[n]%Mod*dfac[m-n]%Mod;
}
signed main(){
n=read();
int tmp=ksm(3,n);
pw[0]=1;for(int i=1;i<=n;++i)pw[i]=pw[i-1]*tmp%Mod;
fac[0]=dfac[0]=fac[1]=dfac[1]=inv[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%Mod;
inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
dfac[i]=dfac[i-1]*inv[i]%Mod;
}
int ans=0,w=tmp-3,buf=1;
for(int i=1;i<=n;++i){
ans=(ans+buf*pw[n-i]*3)%Mod;
buf=buf*w%Mod;
}
int iv=ksm(w,Mod-2);
for(int i=1;i<=n;++i){
buf=buf*iv%Mod;
int tmp=3*C(n,i)%Mod*ksm(ksm(3,n-i)-1,n)%Mod;
tmp=(tmp+(ksm(3,i)-3)*C(n,i)%Mod*ksm(ksm(3,n-i),n))%Mod;
tmp=tmp%Mod;
if(i-1&1) tmp=Mod-tmp;
ans=(ans+tmp)%Mod;
}
printf("%lld\n",ans);
return 0;
}
```