[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个格子中都放满炮的的情况外，其它的都可以.

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

Source

Day2

要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_back
using 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;
}

7

1 3