CF997C Sky Full of Stars
题解
一眼组合意义来解,考虑使用二项式反演。
我们设:
- F(i,j) 表示钦定有 i 行、j 列同色,其余任意的方案数。
- G(i,j) 表示恰好有 i 行、j 列同色的方案数。
答案即为 3n2−G(0,0)。
由于 G 两个维度互相独立,我们使用两次二项式反演:
G(x,y)=i=x∑nj=y∑n(−1)i+j−x−y(xi)(yj)F(i,j)
所以:
G(0,0)=i=0∑nj=0∑n(−1)i+jF(i,j)
接下来考虑如何快速计算 F(i,j):
- i,j=0:所有钦定行颜色相同,即:
F(i,j)=(in)(jn)⋅3⋅3(n−i)(n−j)
- j=0:被钦定的行可以是任意颜色,即:
F(i,0)=(in)⋅3i⋅3n(n−i)
- i=0 同理。
- i=j=0:随便填,F(0,0)=3n2。
接下来考虑 G(0,0) 怎么算:
- i,j=0:
S1=i=1∑nj=1∑n(−1)i+jF(i,j)=i=1∑nj=1∑n(−1)j+i(in)(jn)3(n−i)(n−j)+1=3n2+1i=1∑n(in)(−1)i3−inj=1∑n(jn)(−1)j3j(i−n)=3n2+1i=1∑n(in)(−1)i3−in((1−3i−n)n−1)
- i,j 有一个为 0,只需要算一个,乘 2 即可:
S2=2i=1∑n(−1)i(in)i+n(n−i)=2⋅3n2[i=1∑n(in)(−1)i3i(1−n)]=2⋅3n2((1−31−n)n−1)
- i=j=0,S3=3n2。
所以 G(0,0)=S1+S2+S3。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const ll MOD = 998244353;
ll n;
ll pow3[N] , fac[N] , invfac[N];
ll qmi(ll a , ll b) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % MOD;
a = a * a % MOD; b >>= 1;
}
return res;
}
void add(ll &a , ll b) {
a += b;
if(a >= MOD) a -= MOD;
else if(a < 0) a += MOD;
}
ll C(ll x , ll y) {
return fac[x] * invfac[y] % MOD * invfac[x-y] % MOD;
}
void init() {
pow3[0] = 1; fac[0] = 1;
for(int i = 1 ; i <= n ; i ++) {
pow3[i] = pow3[i-1] * 3ll % MOD;
fac[i] = fac[i-1] * i % MOD;
}
invfac[n] = qmi(fac[n] , MOD-2);
for(int i = n ; i >= 1 ; i --) {
invfac[i-1] = invfac[i] * i % MOD;
}
}
int main() {
scanf("%lld" , &n);
init();
ll ans = qmi(3 , n*n+1) , res = 0;
for(int i = 1 ; i <= n ; i ++) {
add(res , C(n,i) * (i&1 ? -1 : 1) * ((qmi(1-pow3[i] * qmi(pow3[n], MOD-2) % MOD , n)-1) % MOD + MOD) % MOD
* qmi(qmi(3,n*i) , MOD-2) % MOD);
}
ans = ans * res % MOD;
add(ans , 2ll * qmi(3,n*n) % MOD * ((qmi(1-qmi(pow3[n-1],MOD-2) , n)-1)%MOD + MOD) % MOD);
ans = (MOD-ans)%MOD;
printf("%lld\n" , ans);
return 0;
}(相当不美观)。
