Paint Box

一直不是很懂容斥原理的原因,学二分图的时候再看看!
我们很容易知道,求给n个位子上色,可以最多使用k种颜色的方案数是.
由容斥原理想到可以把最多->等于.
那么就是最多使用k种颜色-最多使用k-1种颜色+最多使用k-2种颜***r>那么直接这样做就好了.
(值得注意的是:因为取模了,所以会存在负数的情况,记得对负数取模~)
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e6+5;
ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }return res;
}

ll f[N],ivf[N];
void init()
{
    f[0]=1;
    for(ll i=1;i<=N-5;i++)    f[i]=f[i-1]*i%mod;
    ivf[N-5]=qp(f[N-5],mod-2);
    for(ll i=N-5;i>=1;i--)    ivf[i-1]=ivf[i]*i%mod;
}

ll C(ll a,ll b)
{
    return f[a]*ivf[b]%mod*ivf[a-b]%mod;    
}

ll cal(ll n,ll k)
{
    ll res=0,fm=k;int pd=1;
    while(k)
    {
        if(pd&1)    res+=C(fm,k)%mod*k%mod*qp(k-1,n-1)%mod;
        else        res-=C(fm,k)%mod*k%mod*qp(k-1,n-1)%mod;
        res=(res%mod+mod)%mod;
        pd++,k--;
    }return res;
}

int main()
{
    int T;scanf("%d",&T);
    init();
    while(T--)
    {
        ll n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
        ll fm=1;for(int i=k;i>1;i--)    fm=fm*i%mod;
        fm=qp(fm,mod-2);ll fz=1;
        for(int i=m;i>m-k;i--)    fz=fz*i%mod;
        ll ans=cal(n,k)*fz%mod*fm%mod;
        printf("%lld\n",ans);
    }
    return 0;
}