题目概述

构造一个 $n\times m$ 的矩阵，矩阵元素的值是 $[1,K]$ 中的整数。如果一个元素的值是同行同列中最大的，那么就是一个JZ数。令 $A_g$ 表示构造出的矩阵有 $g$ 个JZ数的方案数，求 $\sum_{g=0}^{nm}(g+1)A_g$ 。

解题报告

也就是求 $\sum_{g=0}^{nm}gA_g+\sum_{g=0}^{nm}A_g$ ，你会发现 $g$ 显然到不了 $nm$ 级别，所以就是求 $\sum_{g=0}^{min\{n,m\}}gA_g$ 和 $\sum_{g=0}^{min\{n,m\}}A_g$ 。我会告诉你这然并卵吗。

直接求 $A_g$ 很难求，更别说 $gA_g$ 了，根据套路我们考虑 $A_g$ 和 $gA_g$ 的意义。由于 $A_g$ 表示方案数，那么总方案数的意义是什么？你看一个方案显然对应一个矩阵……所以 $\sum_{g=0}^{nm}A_g=K^{nm}$ 啊23333。

那 $gA_g$ 是什么意思？可以理解为每个方案中的每一个JZ数都提供了 $1$ 的贡献，所以 $\sum_{g=0}^{nm}gA_g$ 就是每个位置作为JZ数的方案的和。也就是 $nm\sum_{k=2}^{K}(k-1)^{(n-1)+(m-1)}\cdot K^{(n-1)(m-1)}$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int MOD=1e9+7;

int te,n,m,K,ans;

inline int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;}return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    for (int t=(scanf("%d",&te),1);t<=te;t++){
        scanf("%d%d%d",&n,&m,&K);ans=0;for (int k=2;k<=K;k++) AMOD(ans,Pow(k-1,n+m-2));
        ans=(LL)ans*n*m%MOD*Pow(K,(n-1)*(m-1))%MOD;AMOD(ans,Pow(K,n*m));printf("Case #%d: %d\n",t,ans);
    }
    return 0;
}