[Ahoi2009]chess 中国象棋

Time Limit:10000MS Memory Limit:65536K
Total Submit:21 Accepted:11
Case Time Limit:1000MS

Description

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

Input

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

Output

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

Sample Input

Sample Output

Hint

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

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

Source

Day2
61.187.179.132:8080/JudgeOnline/showproblem
要Dp。。非常的复杂，看Code吧。。累死了。。
Code：

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;const int maxn=100+10,mod=9999973;int Dp[2][maxn][maxn],n,m;int C[maxn][maxn]={0};int plus_mod(int&a,int b){ a+=b;return a%=mod;}int multi_mod(int&a,int b){ return a=((long long)a*b)%mod;}void GetC(){ C[0][0]=1; for(int i=1;i<=m;i++) { C[i][0]=C[i][i]=1; for(int j=1;j<i;j++) { C[i][j]=C[i-1][j-1]+C[i-1][j]; C[i][j]%=mod; } }}#define MM(x) memset(x,0,sizeof(x))int main(){ cin>>n>>m;int now=0,next=1; MM(Dp);GetC(); Dp[next][m][0]=1; for(int i=0;i<n;i++) { swap(now,next); MM(Dp[next]); for(int a0=0;a0<=m;a0++) for(int a1=0;a1+a0<=m;a1++) if(Dp[now][a0][a1]) { int x=Dp[now][a0][a1],c; //Dont used Row i plus_mod(Dp[next][a0][a1],x); //Put one if(a0) { c=x; multi_mod(c,C[a0][1]); plus_mod(Dp[next][a0-1][a1+1],c); } if(a1) { c=x; multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0][a1-1],c); } //Put two if(a0>=2) { c=x; multi_mod(c,C[a0][2]); plus_mod(Dp[next][a0-2][a1+2],c); } if(a1>=2) { c=x; multi_mod(c,C[a1][2]); plus_mod(Dp[next][a0][a1-2],c); } if(a0&&a1) { c=x; multi_mod(c,C[a0][1]); multi_mod(c,C[a1][1]); plus_mod(Dp[next][a0-1][a1],c); } } } int ans=0; rep(i,m+1)rep(j,m+1)plus_mod(ans,Dp[next][i][j]); cout<<ans<<endl;}71 3