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
正解：$dp$。
设$f[i][j][k]$表示前$i$行，有$j$列没有填炮，有$k$列填了一个炮。
那么转移分为$6$种情况：
1.当前行不放炮；
2.当前行放一个炮在没有炮的列上；
3.当前行放一个炮在有一个炮的列上；
4.当前行放两个炮在两个没有炮的列上；
5.当前行放两个炮在一个没有炮且一个有一个炮的列上；
6.当前行放两个炮在两个有一个炮的列上。
然后用乘法原理随便转移一下就行了。
1 #include <bits/stdc++.h> 2 #define il inline 3 #define RG register 4 #define ll long long 5 #define rhl (9999973) 6 7 using namespace std; 8 9 int f[110][110][110],n,m,ans; 10 ll res; 11 12 il int gi(){ 13 RG int x=0,q=1; RG char ch=getchar(); 14 while ((ch<'0' || ch>'9') && ch!='-') ch=getchar(); 15 if (ch=='-') q=-1,ch=getchar(); 16 while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); 17 return q*x; 18 } 19 20 int main(){ 21 #ifndef ONLINE_JUDGE 22 freopen("chess.in","r",stdin); 23 freopen("chess.out","w",stdout); 24 #endif 25 n=gi(),m=gi(),f[0][m][0]=1; 26 for (RG int i=1;i<=n;++i) 27 for (RG int j=0;j<=m;++j) 28 for (RG int k=0;j+k<=m;++k){ 29 res=f[i-1][j][k]; 30 if (j+1<=m && k) res+=1LL*f[i-1][j+1][k-1]*(j+1); 31 if (j+k+1<=m) res+=1LL*f[i-1][j][k+1]*(k+1); 32 if (j+2<=m && k>=2) res+=1LL*f[i-1][j+2][k-2]*(j+2)*(j+1)>>1; 33 if (j+k+1<=m) res+=1LL*f[i-1][j+1][k]*(j+1)*k; 34 if (j+k+2<=m) res+=1LL*f[i-1][j][k+2]*(k+2)*(k+1)>>1; 35 f[i][j][k]=res%rhl; 36 } 37 for (RG int i=0;i<=m;++i) 38 for (RG int j=0;i+j<=m;++j){ 39 ans+=f[n][i][j]; if (ans>=rhl) ans-=rhl; 40 } 41 printf("%d ",ans); return 0; 42 }