BZOJ_1801_[Ahoi2009]chess 中国象棋_DP

时间:2021-08-01 16:19:29

BZOJ_1801_[Ahoi2009]chess 中国象棋_DP

Description

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

Input

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

Output

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

Sample Input

1 3

Sample Output

7

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);
}