容斥

题面

给一个 n*m 的矩阵染色，每个点可以染 k 种颜色，求没有任意一行或任意一列颜色相同的方案数。答案对 998244353 取模。

容斥。
枚举有 i 行 j 列同色的方案数，并乘上 $(-1)^{i+j}$ 加入答案。//容斥原理，有加有减
令 f(i; j) 为 i 行 j 列同色，同色的行列所能取的颜色方案数。
i = 0; j = 0 时， f(i; j) = 1 //没有点，自然只有一种选择。
i = 0; j > 0 时， f(i; j) = $k^{j}$ //只有列有同色，每一列有k种选择，共j列
i > 0; j = 0 时， f(i; j) = $k^{i}$ //同上
i > 0; j > 0 时， f(i; j) = k //这i行j列颜色都一样，只有k种选择
答案为 $sum_{i=0}^{n}$ $sum_{j=0}^{m}$ $(-1)^{i+j}$ * $_{n}^{i} extrm{C}_{m}^{j} extrm{C}$ * f(i; j) * $k^{(n-i)(m-j)}$
对于 i = 0 或 j = 0 的情况可以暴力计算，考虑 i 和 j 都大于 0 的情况。
k $sum_{i-1}^{n}$ $sum_{j=1}^{m}$ $(-1)^{(i+j)}$ * $_{n}^{i} extrm{C}_{m}^{j} extrm{C}$ * $k^{(n-i)(m-j)}$
= k $sum_{i-1}^{n}$ $(-1)^{i}$ $_{n}^{i} extrm{C}$ $sum_{j=1}^{m}$ $(-1)^{j}$ $_{m}^{j} extrm{C}$ · $k^{(n-i)(m-j)}$
= k $sum_{i-1}^{n}$ $(-1)^{i}$ $_{n}^{i} extrm{C}$ $sum_{j=1}^{m}$ $(-1)^{j}$ $_{m}^{j} extrm{C}$ · $k^{(n-i)^{(m-j)}}$
= k $sum_{i-1}^{n}$ $(-1)^{i}$ $_{n}^{i} extrm{C}$ ( $(k^{(n-i)}-1)^{m}$ - $(k^{n-i})^{m}$ )
就可以利用快速幂计算了。

代码

#include<iostream>
using namespace std;
const long long MOD=998244353,MOD2=MOD-1;
const int N=1010000;
long long n,m,k,fac[N],inv[N];
long long pow(long a,long b){//快速幂 
    a=(a%MOD+MOD)%MOD,b=(b%MOD2+MOD)%MOD2;
    long long r=1;
    while(b){
        if(b&1) r=r*a%MOD;
        a=a*a%MOD,b<<=1;
    }
    return r;
}
long long C(int n,int m){//组合数 
    if(n<0||m<0||n-m<0) return;
    return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
int main(){
    fac[0]=1;
    for(int i=1;i<=1000000;i++)
        fac[i]=fac[i-1]*i%MOD;//阶乘
    inv[0]=inv[1]=1;//逆元
    for(int i=2;i<=1000000;i++)
        inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    for(int i=1;i<=1000000;i++)
        inv[i]=inv[i-1]*inv[i]%MOD;
    cin>>n>>m>>k;
    long long ans=pow(k,n*m);//所有的情况 
    for(int i=1;i<=n;i++)//暴力求只有横行同色 
        if(i&1)//容斥原理，奇减偶加 
            ans=(ans-C(n,i)*pow(k,i)%Mod*pow(k,(n-i)*m)%MOD+MOD)%MOD;
        else
            ans=(ans+C(n,i)*pow(K,i)%MOD*pow(K,(n-i)*m)%MOD)%MOD;
    for(int i=1;i<=m;i++)//暴力求只有竖列同色 
        if(i&1)
            ans=(ans-C(m,i)*pow(K,i)%MOD*pow(K,(m-i)*n)%MOD+MOD)%MOD;
        else
            ans=(ans+C(m,i)*pow(K,i)%MOD*pow(K,(m-i)*n)%MOD)%MOD;
    for(int i=1;i<=n;i++)//求既有行又有列同色 
        if(i&1)
            ans=(ans-C(n,i)*K%MOD*((pow(pow(K,n-i)-1,m)-pow(K,(n-i)*m)+MOD)%MOD)%MOD+MOD)%MOD;
        else
            ans=(ans+C(n,i)*K%MOD*((pow(pow(K,n-i)-1,m)-pow(K,(n-i)*m)+MOD)%MOD)%MOD)%MOD;
    cout<<ans;
    return 0;
}

欢迎指正评论O(∩_∩)O~~