Rikka with Nash Equilibrium
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1460 Accepted Submission(s): 591
Rikka and Yuta are playing a simple matrix game. At the beginning of the game, Rikka shows an n×m integer matrix A. And then Yuta needs to choose an integer in [1,n], Rikka needs to choose an integer in [1,m]. Let i be Yuta's number and j be Rikka's number, the final score of the game is Ai,j.
In the remaining part of this statement, we use (i,j) to denote the strategy of Yuta and Rikka.
For example, when n=m=3 and matrix A is
If the strategy is (1,2), the score will be 2; if the strategy is (2,2), the score will be 4.
A pure strategy Nash equilibrium of this game is a strategy (x,y) which satisfies neither Rikka nor Yuta can make the score higher by changing his(her) strategy unilaterally. Formally, (x,y) is a Nash equilibrium if and only if:
In the previous example, there are two pure strategy Nash equilibriums: (3,1) and (2,2).
To make the game more interesting, Rikka wants to construct a matrix A for this game which satisfies the following conditions:
1. Each integer in [1,nm] occurs exactly once in A.
2. The game has at most one pure strategy Nash equilibriums.
Now, Rikka wants you to count the number of matrixes with size n×m which satisfy the conditions.
The first line of each testcase contains three numbers n,m and K(1≤n,m≤80,1≤K≤109).
The input guarantees that there are at most 3 testcases with max(n,m)>50.
在一个矩阵中,如果仅有一个数同时是所在行所在列最大值,那么这个数满足纳什均衡。
构造一个n*m的矩阵,里面填入[1,n*m]互不相同的数字,求有多少种构造方案。
由题可得,满足纳什均衡的数一定是最大值n*m。因此我们可以从大往小依次将数填入矩阵,小数依附于大数的行或列,由此产生的三种行为:
1.所在列有大数,行+1 数+1
2.所在行有大数,列+1 数+1
3.所在行列都有大数,位于交界处,数+1
dp三种状态[占有行数][占有列数][占有个数]进行求解。因为本题数据很强,所以需要以下优化:
1.尽可能得减少取模次数
2.注意状态与遍历顺序保持一致
//记忆化搜索
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod,n,m;
ll dp[][][];
ll dfs(ll x,ll y,ll z){
if(dp[x][y][z]>-) return dp[x][y][z];
ll tmp=;
if(x<n) tmp+=y*(n-x)*dfs(x+,y,z+)%mod;
if(y<m) tmp+=x*(m-y)*dfs(x,y+,z+)%mod;
if(x*y>z) tmp+=(x*y-z)*dfs(x,y,z+)%mod;
return dp[x][y][z]=tmp;
}
int main()
{
ll t;
scanf("%lld",&t);
while(t--){
memset(dp,-,sizeof(dp)); //答案有0的情况,因此初始化为-1
scanf("%lld%lld%lld",&n,&m,&mod);
dp[n][m][n*m]=;
ll ans=n*m*dfs(,,)%mod;
printf("%lld\n",ans);
}
}
//dp
#include<bits/stdc++.h>
#define MAX 82
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll; ll dp[MAX][MAX][]; //注意顺序 int main()
{
int t,n,m,MOD,i,j,k;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&MOD);
memset(dp,,sizeof(dp));
dp[][][]=n*m;
for(i=;i<=n;i++){
for(j=;j<=m;j++){
for(k=;k<n*m;k++){ //注意顺序
dp[i+][j][k+]+=(n-i)*j*dp[i][j][k];
if(dp[i+][j][k+]>=MOD) dp[i+][j][k+]%=MOD;
dp[i][j+][k+]+=(m-j)*i*dp[i][j][k];
if(dp[i][j+][k+]>=MOD) dp[i][j+][k+]%=MOD;
if(i*j>k){
dp[i][j][k+]+=(i*j-k)*dp[i][j][k];
if(dp[i][j][k+]>=MOD) dp[i][j][k+]%=MOD;
}
}
}
}
printf("%lld\n",dp[n][m][n*m]%MOD);
}
return ;
}