bzoj1801 [Ahoi2009]中国象棋

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

正解：$dp$。

设$f[i][j][k]$表示前$i$行，有$j$列没有填炮，有$k$列填了一个炮。

那么转移分为$6$种情况：

1.当前行不放炮；

2.当前行放一个炮在没有炮的列上；

3.当前行放一个炮在有一个炮的列上；

4.当前行放两个炮在两个没有炮的列上；

5.当前行放两个炮在一个没有炮且一个有一个炮的列上；

6.当前行放两个炮在两个有一个炮的列上。

然后用乘法原理随便转移一下就行了。

 #include <bits/stdc++.h>

 #define il inline

 #define RG register

 #define ll long long

 #define rhl (9999973)

 using namespace std;

 int f[][][],n,m,ans;

 ll res;

 il int gi(){

   RG int x=,q=; RG char ch=getchar();

   while ((ch<'' || ch>'') && ch!='-') ch=getchar();

   if (ch=='-') q=-,ch=getchar();

   while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

   return q*x;

 }

 int main(){

 #ifndef ONLINE_JUDGE

   freopen("chess.in","r",stdin);

   freopen("chess.out","w",stdout);

 #endif

   n=gi(),m=gi(),f[][m][]=;

   for (RG int i=;i<=n;++i)

     for (RG int j=;j<=m;++j)

       for (RG int k=;j+k<=m;++k){

     res=f[i-][j][k];

     if (j+<=m && k) res+=1LL*f[i-][j+][k-]*(j+);

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

     if (j+<=m && k>=) res+=1LL*f[i-][j+][k-]*(j+)*(j+)>>;

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

     if (j+k+<=m) res+=1LL*f[i-][j][k+]*(k+)*(k+)>>;

     f[i][j][k]=res%rhl;

       }

   for (RG int i=;i<=m;++i)

     for (RG int j=;i+j<=m;++j){

       ans+=f[n][i][j]; if (ans>=rhl) ans-=rhl;

     }

   printf("%d\n",ans); return ;

 }

巴特西