hdu-6415 计数DP

Nash Equilibrium is an important concept in game theory.

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

⎡⎣⎢111241131⎤⎦⎥

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:

{Ax,y≥Ai,y ∀i∈[1,n]Ax,y≥Ax,j ∀j∈[1,m]

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.

InputThe first line contains a single integer t(1≤t≤20), the number of the testcases.

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.OutputFor each testcase, output a single line with a single number: the answer modulo K.Sample Input

Sample Output

64

1170

OJ-ID：
hdu-6415

author：
Caution_X

date of submission：
20191026

tags：
dp

description modelling：
给定N×M的矩阵A，若该矩阵满足{A(x,y)≥A(i,y) ?i∈[1,n],A(x,y)≥A(x,j) ?j∈[1,m]}且该矩阵元素分别是1~N*M，则称这是矩阵A的一个方案。输入N,M,K，输出N×M矩阵的方案数模K的值。

major steps to solve it：
从最大的数开始依次选择一个位置来存放，第一个数有N×M种放置方法，后面每一个数都必须保证和之前放过的数同一行或者同一列。
首先第一个数会产生一个新行和一个新列，第二个数会产生一个新行或者一个新列，第三个数同第二个数，第四个数及第四个数之后的所有数都分三种情况讨论：
（1）新加入之后产生了一个新行
（2）新加入之后产生了一个新列
（3）既没有产生新行也没有产生新列
设dp[i][j][k]，表示已经产生了i个行，j个列，用掉了k个数
那么则:
（1）dp[i][j][k]+=dp[i][j][k-1]*(i*j-i+1)%MOD，没有产生新行或者新列
（2）dp[i][j][k]+=dp[i-1][j][k-1]*(n-i+1)%MOD，产生了新行
（3）dp[i][j][k]+=dp[i][j-1][k-1]*(m-j+1)%MOD，产生了新列

AC code:

#include <iostream>

#include <string.h>

#include <stdio.h>

using namespace std;

typedef long long int LL;

LL T, n, m, mod, dp[][][], p;

int main()

{

    scanf("%lld", &T);

    while(T--) {

        scanf("%lld%lld%lld", &n, &m, &mod);

        memset(dp, , sizeof dp); p = ;

        dp[][][] = n * m % mod;

        for(int i=;i<=n*m;i++,p^=) {

            for(int j=;j<=n;j++) {

                for(int k=;k<=m;k++) {

                    dp[j][k][p] = ;

                    if(j * k < i) continue;

                    dp[j][k][p] = dp[j][k][p^] * (j*k-i+) % mod;

                    dp[j][k][p] = (dp[j][k][p] + dp[j-][k][p^] * (n-j+) * k) % mod;

                    dp[j][k][p] = (dp[j][k][p] + dp[j][k-][p^] * (m-k+) * j) % mod;

                }

            }

        }

        printf("%lld\n", dp[n][m][p^]);

    }

    return ;

}

巴特西

hdu-6415 计数DP

最新文章

热门文章