题意
给两个整数n，m，让你构造一个矩阵n*m的矩阵，此矩阵满足一下两点：
1.只有一个元素在它的此行和此列中都是最大的（纳什均衡点）。
2.矩阵中1~n*m中的数都恰好出现一次。
问有多少种构造方法？
题解
从大到小的放，下一个数需要放在已经被放过数的的行和列上，不然这个点就会成为新的纳什均衡点。
我们设dp(i,j,k)表示当前已经放了i个数且有j行k列被放过数了。那么就有三种状态转移。
1.下一个数可以放在新的一行dp[i+1][j+1][k] += k*(n-j)*dp[i][j][k]（第i+1个数放的方法有k*(n-j)种）
2.下一个数可以放在新的一列dp[i+1][j][k+1] += j*(m-k)*dp[i][j][k]（第i+1个数放的方法有j*(m-k)种）
3.下一个数放在了已有行列的交点上dp[i+1][j][k] += (j*k-i)*dp[i][j][k]（第i+1个数放的方法有(j*k-i)种）
代码
#include <iostream> #include <stdio.h> #include <algorithm> #include <math.h> #include <map> #include <vector> #include <string.h> using namespace std; const int maxn = 82; typedef long long ll; int mod; ll dp[2][maxn][maxn]; int n, m; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d%d", &n, &m, &mod); memset(dp, 0, sizeof(dp)); dp[0][1][1] = n*m; int ne, now = 0; for(int i = 2; i <= n*m; i++) { ne = now^1; memset(dp[ne], 0, sizeof(dp[ne])); for(int j = 1; j <= n; j++) { for(int k = 1; k <= m; k++) { if(dp[now][j][k]) { dp[ne][j+1][k] = (dp[ne][j+1][k]+dp[now][j][k]*(n-j)*k)%mod; dp[ne][j][k+1] = (dp[ne][j][k+1]+dp[now][j][k]*(m-k)*j)%mod; ll p=j*k-i+1; dp[ne][j][k]=dp[ne][j][k]+p*dp[now][j][k]%mod; } } } now = ne; } printf("%I64d\n",dp[now][n][m]%mod); } return 0; }
