ZigZagK的博客
[DP]HDU6415(2018多校训练赛第九场)【Rikka with Nash Equilibrium】题解
[DP]HDU6415(2018多校训练赛第九场)【Rikka with Nash Equilibrium】题解
2018年8月21日 08:03
HDU
查看标签

题目概述

有 $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}$ 就是答案。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
#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协议 许可协议。转载请注明出处!
本文写于 2419 天前,最后更新于 2419 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏