HDU6415(DP)

xiaoxiao2021-03-01  25

题意

给两个整数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; }

 

转载请注明原文地址: https://www.6miu.com/read-4049949.html

最新回复(0)