个人认为是道很好的组合加容斥练习题。

Solution

考虑将行，列，颜色的限制分开处理。

先限制颜色。

令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数，

$$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$

再限制列。

令 $g(i,j)$ 为只是用 $i$ 种颜色，只填 $j$ 列的方案数。

$$ f(i)=\sum\limits_{j=0}^m\dbinom{m}{j}(-1)^{c-j}g(i,j) $$

最后

$$ g(i,j)=((i+1)^j-1)^n $$

带入求解即可，时间复杂度 $O(mc\log n)$ 。

Code

#include<bits/stdc++.h>
#define N 505
#define int long long
using namespace std;

int read(){
    int x=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*w;
}

const int mod = 1e9+7;
int n,m,c,ans;
int fac[N],ifac[N],a[N],f[N];

int qpow(int x,int k){
    int res=1;
    while(k){
        if(k&1) res=res*x%mod;
        x=x*x%mod;k>>=1;
    }
    return res;
}
void init(){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=400;++i) fac[i]=fac[i-1]*i%mod;
    ifac[400]=qpow(fac[400],mod-2);
    for(int i=399;i>=1;--i) ifac[i]=ifac[i+1]*(i+1)%mod;
}
int C(int x,int y){ return fac[x]*ifac[y]%mod*ifac[x-y]%mod; }

signed main(){
    init();
    n=read();m=read();c=read();
    for(int i=0;i<=c;++i)
        for(int j=m,opt=1;j>=0;--j,opt*=-1){
            int x=opt*C(m,j)*qpow((qpow(i+1,j)-1+mod)%mod,n)%mod;
            f[i]=(f[i]+x+mod)%mod;
        }
    for(int i=c,opt=1;i>=0;--i,opt*=-1) ans=(ans+opt*C(c,i)%mod*f[i]%mod+mod)%mod;
    printf("%lld\n",ans);
    //for(int i=0;i<=c;++i) cout<<f[i]<<endl;
    return 0;
}