CodeForces - 997C Sky Full of Stars

组合数学

题目链接

CodeForces - 997C Sky Full of Stars

题解

设$f(i,j)$表示至少有i行j列一种颜色的方案数
可以发现，当ij有相交时颜色只能为一种
那么对于$i=0 || j=0$时$f(i,j) = C_n^i * C_n^j*3^{(n - i) *(n - j) + i + j}$
否则$f(i,j) = C_n^i * C_n^j*3^{(n - i) * (n - j) + 1}$
可以得到一种很显然的容斥方法
对于第一种情况单独算，复杂度$nlogn$
对于第二个式子，容斥是$n^2$的,推式子
$3\sum_{i=1}^{n}\sum_{j=1}^{n}{C_n^iC_n^j(-1)^{i+j+1}3^{(n-i)(n-j)}}$
设$T=3^{ij}$换元$3^{(n - i)*(n - j)}$
原式$=3\sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1}C_n^iC_n^j(-1)^{i + j - 1}3^{ij}$
拆$(-1)^{i + j + 1}$
$=3\sum_{i = 0}^{n - 1}C_n^i(-1)^{i + 1}\sum_{j = 0}^{n - 1}C_n^j(-3^i)^{j}$
另$T=(-3)^i$
对于后面那部分二项式因式分解
$=3\sum_{i = 0}^{n - 1} C_n^i (-1)^{i + 1} *[(1 + T)^n - T^n]$
复杂变成了$nlogn$

代码

#include<bits/stdc++.h> 
using namespace std;  
#define int long long 
const int maxn = 1000007; 
const int mod = 998244353; 
int n,fac[maxn],inv[maxn]; 
int fstpow(int x,int y) { 
    x %= mod; 
    int ret = 1; 
    for(; y; y >>= 1,x = 1ll * x * x % mod) 
        if(y & 1)  ret = 1ll * ret * x % mod; 
    return ret; 
}  
int calc(int x,int y) { 
    return 1ll * ((fac[x] * inv[y]) % mod) * (inv[x - y]) % mod; 
} 
void get_inv() { 
    fac[0] = 1,inv[0] = 1; 
    for(int i = 1;i <= n;i++) { 
        fac[i] = 1ll * fac[i - 1] * i % mod;  
        inv[i] = fstpow(fac[i],mod - 2);  
    }    
}   
main() { 
    scanf("%I64d",&n);  
    get_inv();  
    int ans1 = 0;  
    for(int a,b,i = 1;i <= n;i++) { 
        a = 1ll * calc(n,i) * fstpow(-1,i + 1) % mod; 
        b = fstpow(3, (1ll * n * (n - i) + i) % (mod - 1)); 
        ans1 = (ans1 + (1ll * a * b % mod)) % mod; 
    } 
    ans1 = 2 * ans1 % mod; 
    int ans2 = 0; 
    for(int t,b,a,i = 0;i < n;i++) {     
        a = 1ll * calc(n,i) * fstpow(-1,i + 1) % mod; 
        t = mod - fstpow(3,i); 
        b = (fstpow(t + 1,n) + mod - fstpow(t,n)) % mod; 
        ans2 = (ans2 + (1ll * a * b) % mod) % mod;  
    } 
    //int tmp = 
    printf("%I64d\n",(((ans1 + 1ll * ans2 * 3) % mod) + mod) % mod); 
    return 0; 
}