1801: [Ahoi2009]chess 中国象棋

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2520 Solved: 1524
[Submit][Status][Discuss]

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

Source

Day2

每行只存在3中情况，不放，放一个棋子，放两个棋子，标准3进制状压DP

设动规数组f[i][j][k]，表示前i行中，有j列有一个棋子，有k列有两个棋子

那么第i行有6种放置情况

1、不放

2、一个棋子，放到没有棋子的列

3、一个棋子，放到有一个棋子的列

4、两个棋子，都放到没有棋子的列

5、两个棋子，一个放到没有棋子的列，另一个放到有一个棋子的列

6、两个棋子，两个分别放到有一个棋子的列

第一次f[i][j][k]忘记取模爆了。。。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 #define LL long long

 const int mod=;

 LL n,m,ans;

 LL f[][][];

 LL C(LL x)

 {

     return x*(x-)/;

 }

 int main()

 {

     cin>>n>>m;

     f[][][]=;

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

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

             for(int k=;k<=m-j;k++)

             {

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

                 if(j) f[i][j][k]+=f[i-][j-][k]*(m-j-k+);

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

                 if(j>=) f[i][j][k]+=f[i-][j-][k]*C(m-j-k+);

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

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

                 f[i][j][k]%=mod;

             }

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

         for(int k=;k<=m-j;k++)

             ans+=f[n][j][k];

     ans%=mod;

     cout<<ans;

     return ;

 }

巴特西