[2016-2017 ACM-ICPC CHINA-Final][GYM 101194 H] Great Cells

    题意：在一个n*m的矩阵内填整数，数字在\([1...K]\)范围内。矩阵中某格的数为great number当且仅当与它同行同列的数字都严格比它小。即\(A_g\)为矩阵中恰有g个great number的填数方案数，求\(\sum_{g=0}^{nm}{(g+1)A_g}\)。(\(n,m,k<=200\))

    题解：显然\(sum_{g=0}^{nm}{(g+1)A_g}=\sum_{g=0}^{min\{n,m\}}{(g+1)A_g}\)，这个就不多说了。

    很明显地可以发现\(\sum{A_g}\)就是所有填数方案数，即\(K^{nm}\)。剩下要求的就是\(\sum{gA_g}\)。

    刚开始想前面那个式子\(\sum{A_g}\)能构造出对应的方案，那么这个应该也行？然而搞了半天想不出来怎么构造...

    事实上，\(\sum{gA_g}\)就是只要一个格子里的数为great number，就对当前方案计数一次。理解起来就是，一个有g个great number的矩阵，我对每个great number都计数一次当前方案数，那么结果就是g倍的当前方案数了。可以得到\[\sum{gA_g} = nm\sum_{i=2}^{k}{(i-1)^{n+m-2}}\cdot k^{(n-1)(m-1)}\]

#include <bits/stdc++.h>
using namespace std;
const int maxn=210,mo=1e9+7;

int Pow(int x,int p)
{
	long long res=1,xx=x;
	while (p)
	{
		if (p&1) (res*=xx)%=mo;
		(xx*=xx)%=mo;
		p>>=1;
	}
	return (int)res;
}

int n,m,k;

int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++)
	{
		printf("Case #%d: ",t);
		scanf("%d%d%d",&n,&m,&k);
		int ans=0;
		for (int i=2;i<=k;i++)
			(ans+=(long long)Pow(i-1,n+m-2)*Pow(k,(n-1)*(m-1))%mo)%=mo;
		ans=(long long)ans*n*m%mo;
		ans=(ans+Pow(k,n*m))%mo;
		printf("%d\n",ans);
	}
	return 0;
}