「AHOI2009」中国象棋

发表于 | 分类于 | | 浏览量： 次

数数万岁…

前言

早晨起床，打开电脑，上了洛谷，打了个卡，发现智能推荐里面有几道上古时代的省选题。随便戳开了一道，发现是个应该是个DP数数题，而我数数又很差，正想补补，于是就很愉快的做起了此题…

传送门

洛谷P2051

BZOJ1801

题解

感觉2010年之前的省选题都不怎么难、代码量都不大(对于个别题目当我没说)…

首先很显然，每一行每一列里，如果炮的个数都≤2，那么都是合法的啦！

看了一眼，数据范围很亲切，然后就自然而然地想出了这样一个DP：（汗

首先是初始值$F[0][0][0]=1​$。

然后考虑怎么从第$i-1$行转移过来。

如果第$i$行一个炮也不放，那么就有$F[i][j][k]=F[i-1][j][k]$。

如果放一个，那么有两种情况：

  • 放在空的列上： $F[i][j][k]+=F[i-1][j][k-1]*(m-j-k+1)​$；
  • 放在只放了1个炮的列上： $F[i][j][k]+=F[i-1][j-1][k+1]*(k+1)​$。

如果放两个炮，那么有三种情况：

  • 两个都放在空的列上：$F[i][j][k]+=F[i-1][j][k-2]\cdot(m-j-k+2)\cdot(m-j-k+1)/2$；
  • 一个放在空列，一个放在只有一个的列上：$F[i][j][k]+=F[i-1][j-1][k]\cdot k\cdot(m-j-k+1)$；
  • 两个都放在只有一个的列上：$F[i][j][k]+=F[i-1][j-2][k+2]\cdot(k+2)\cdot(k+1)/2$。

最后的答案：

然后这题就做完了QwQ。

代码

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
27
28
29
30
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=105,TT=9999973;
int n,m,F[maxn][maxn][maxn],ans;
int main()
{
	scanf("%d%d",&n,&m);F[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int k=0;j+k<=m;k++)
			{
				F[i][j][k]=F[i-1][j][k];//这题的模数比较小，有些地方不需要马上模，可以写好看一点
				if(k>=1) F[i][j][k]+=F[i-1][j][k-1]*(m-j-k+1);
				if(j>=1) F[i][j][k]+=F[i-1][j-1][k+1]*(k+1);
				if(k>=2) F[i][j][k]+=F[i-1][j][k-2]*(LL)(m-j-k+2)*(m-j-k+1)/2%TT;
				if(j>=1) F[i][j][k]+=F[i-1][j-1][k]*(LL)k*(m-j-k+1)%TT;
				if(j>=2) F[i][j][k]+=F[i-1][j-2][k+2]*(LL)(k+2)*(k+1)/2%TT;
				F[i][j][k]%=TT;
			}
		}
	}
	for(int j=0;j<=m;j++)
		for(int k=0;j+k<=m;k++)
			ans=(ans+F[n][j][k])%TT;
	printf("%d\n",ans);
	return 0;
}