Gym 101194H Great Cells

题意：

有一张N*M的格子纸，每个格子可以填1到K之间的数。如果一个格子里的数严格大于本行的其他格子里的数，并且严格大于本列的的其他格子里的数，则这个格子叫做Great Cell。Ag表示有Ag种填法使得格子纸中恰有g个Great Cell。

求：

将上面的式子拆开

那么前一项就可以理解为每当格子为Great Cell时就加1，也就是每个格子Great Cell的次数

当前格子填 i 时，同行列只能填 i 以下的数，其他格子任意填

而后一项则是所有填法的和

但是上述式子对n和m同时为1时不成立，因为只有一个格子不会有A₀，所以要单独讨论

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll qpow(ll x,ll n)
{
    ll ans=1;
    while(n)
    {
        if (n&1) ans=ans*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    for(int ca=1;ca<=T;ca++)
    {
        ll n,m,k;
        scanf("%lld%lld%lld",&n,&m,&k);
        printf("Case #%d: ",ca);
        if (n==1&&m==1)
        {
            printf("%lld
",k);
            continue;
        }
        ll ans=0;
        for(int i=1;i<k;i++)
            ans=(ans+n*m*qpow(i,n+m-2)%mod)%mod;
        ans=(ans*qpow(k,(n-1)*(m-1)))%mod;
        ans=(ans+qpow(1LL*k,1LL*n*m))%mod;
        printf("%lld
",ans);
    }
    return 0;
}