menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP]HDU6415(2018多校训练赛第九场)【Rikka with Nash Equilibrium】题解
apps HDU
local_offer 查看标签
comment 0 条评论

题目概述

有 $n\times m$ 的网格,现在要不重复的填入 $1\sim nm$ ,如果一个格子比同行同列的数都大就称这个格子占领了这行这列。求只有一个格子占领一行一列时的方案数。

解题报告

显然 $nm$ 绝对占领一行一列,所以只需要考虑其他格子不占领一行一列就行了。

考虑从大到小放,那么除了 $nm$ 之外其他数都必须放在之前覆盖过的行和列中。

我们发现每个数放下去之后有三种情况:1.处在之前覆盖的列上,占领一行。2.处在之前覆盖的行上,占领一列。3.处在之前的交点,没有占领。

所以定义 $f_{i,j,k}$ 表示已经占领了 $i$ 行 $j$ 列,还剩下 $k$ 个交点的方案数。$f_{1,1,0}=nm$ ,根据三种情况转移一下,然后 $f_{n,m,0}$ 就是答案。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=80,maxk=maxn*maxn;

int n,m,te,MOD,f[maxn+5][maxn+5][maxk+5];

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d",&n,&m,&MOD);
        for (int i=0;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<=n*m;k++) f[i][j][k]=0;f[1][1][0]=n*m;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                for (int k=i*j;~k;k--)
                    if (f[i][j][k]){
                        if (i<n) AMOD(f[i+1][j][k+j-1],(LL)f[i][j][k]*(n*j-i*j)%MOD);
                        if (j<m) AMOD(f[i][j+1][k+i-1],(LL)f[i][j][k]*(m*i-i*j)%MOD);
                        if (k) AMOD(f[i][j][k-1],(LL)f[i][j][k]*k%MOD);
                    }
        printf("%d\n",f[n][m][0]);
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up