hdu6415 Rikka with Nash Equilibrium 2018杭电多校第9场A题【DP】

题目链接：传送门

题意：给你一个n*m矩阵，以及一个mod；

给你一种定义，在矩阵内的某个元素Aij（第i行第j列）在所在的行和列任意一个元素大，为一个平衡。

在这个n*m矩阵中有1~n*m，每个数出现次数为1， 请问有多少种方案构成这个矩阵，答案模mod，且这个矩阵的平衡只有一个。

题解：想了这道题想了很久，赛后看到多校群里的神仙们用oeis推出了公式，真的nb，公式为n!*m!*(n*m)!/(n+m-1)!

我现在都还没想出是怎么找出数列去oeis的， 我看了吉老师的直播，看到dp做法是真的强，万物皆可dp。

思路：每次都是放最大的那个数，第一个数可以随便放，有n*m种放法，第二个数必须得放在已经放的数的同一列或同一行上，由此来写出状态转移方程式，dp[now][j][k]表示当前状态有j行有数字，k列有数字。

AC代码：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long 

using namespace std;

const int N = 82;
ll dp[2][N][N];//状态 行  列 

int main() {
	int t;
	scanf("%d", &t);
	while(t--){
		int n, m, mod;
		scanf("%d%d%d", &n, &m, &mod);
		memset(dp, 0, sizeof dp);
		dp[0][1][1] = n*m;// 状态初始化
		int now = 0;
		for(int i = 2; i <= n*m; i++){
			int ne = now^1;//0->1   1->0
			memset(dp[ne], 0, sizeof dp[ne]);
			for(int j = 0; j <= n; j++){
				for(int k = 0; k <= m; k++){
					if(dp[now][j][k]){
//						printf("%d %d %d %d %d\n",now,i,j,k,dp[now][j][k]);
						ll tot = j*k - i+1;// 没有被占据的交点的个数 
						dp[ne][j][k] = (dp[ne][j][k] + dp[now][j][k] * tot)%mod;//放在交点上 
						dp[ne][j+1][k] = (dp[ne][j+1][k] + dp[now][j][k] * k*(n-j))%mod;//放在某一列上 
						dp[ne][j][k+1] = (dp[ne][j][k+1] + dp[now][j][k] * j*(m-k))%mod;//放在某一行上 
					}
				}
			}
			now = ne;
		}
		printf("%lld\n",dp[now][n][m]); 
	}
	return 0;
}