BZOJ1801:[Ahoi2009]chess 中国象棋

Time Limit: 10 Sec  Memory Limit: 64 MB

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

Source

Day2

用f[i][j][k]在前i行有j行放了一个炮,有k行放了两个炮。

所以这道题的转移有6种

1.不放

2.在未放过的一列放一个

3.在已经放一个的一列放一个

4.在未放过的一列放两个

5.在已经放过一个的两列各放一个

6.分别在未放过的和已经放一个的一列各放一个

#include<cstdio>
typedef long long ll;
const int mod=;
int f[][][];
int main()
{
int n,m,ans=;
scanf("%d%d",&n,&m);
f[][][]=;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
for(int k=;k+j<=m;k++)
{
f[i][j][k]=f[i-][j][k];
if(j) f[i][j][k]+=(ll)(m-j-k+)*f[i-][j-][k]%mod,f[i][j][k]%=mod;
if(k) f[i][j][k]+=((ll)(j+)*f[i-][j+][k-]+(ll)(m-j-k+)*j%mod*f[i-][j][k-])%mod,f[i][j][k]%=mod;
if(k>) f[i][j][k]+=((ll)(j+)*(j+)/%mod*f[i-][j+][k-])%mod,f[i][j][k]%=mod;
if(j>) f[i][j][k]+=(ll)(m-j+-k)*(m-j+-k)/%mod*f[i-][j-][k]%mod,f[i][j][k]%=mod;
if(i==n) ans+=f[i][j][k],ans%=mod;
}
printf("%d",ans);
return ;
}
上一篇:DDD Code First 迁移数据实现EF CORE的软删除,值对象迁移配置


下一篇:阿里云CentOS7系列二 -- 安装Tomcat7的方法