BZOJ_1801_[Ahoi2009]chess 中国象棋_DP

2023-10-06 14:45:16

Description

在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.

Input

一行包含两个整数N，M，中间用空格分开.

Output

输出所有的方案数，由于值比较大，输出其mod 9999973

Sample Input

1 3

Sample Output

HINT

除了在3个格子中都放满炮的的情况外，其它的都可以.

100%的数据中N,M不超过100
50%的数据中，N,M至少有一个数不超过8
30%的数据中，N,M均不超过6

容易知道一行里最多放2个炮。

设F[i][j][k]为当前在第i行有j列放了1个炮，有k列放了2个炮。

这行可能放0,1,2个。

分别乘上组合数转移。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

typedef long long ll;

ll mod=9999973;

ll f[110][110][110];

ll n,m;

int main() {

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

	int i,j,k;

	f[0][0][0]=1;

	for(i=0;i<n;i++) {

		for(j=0;j<=m;j++) {

			for(k=0;j+k<=m;k++) {

				f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%mod;

				if(j+1+k<=m)f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k]*(m-j-k))%mod;

				if(j) f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k]*j)%mod;

				//if(j+k+1<=m)f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*k)%mod;

				if(m-j-k>=2)f[i+1][j+2][k]=(f[i+1][j+2][k]+f[i][j][k]*(m-j-k)*(m-j-k-1)/2)%mod;

				if(j>=2) f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+f[i][j][k]*j*(j-1)/2)%mod;

				if(m-j-k>=1)f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*(m-j-k)*j)%mod;

			}

		}

	}

	ll ans=0;

	for(i=0;i<=m;i++) for(j=0;i+j<=m;j++) ans=(ans+f[n][i][j])%mod;

	printf("%lld\n",ans);

}

码农公寓