http://www.lydsy.com/JudgeOnline/problem.php?id=1801
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1936 Solved: 1120
[Submit][Status][Discuss]
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
#include <cstdlib>
#include <cstdio> const int mod();
const int N();
inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
int n,m,map[N][N];
long long f[N][N][N];
inline long long C(long long x)
{
return x*(x-)>>;
} int Presist()
{
read(n),read(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]; f[i][j][k]%=mod; //此行不放炮
if(j) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]* (m-j+-k))%mod; //该行没有炮的一列放一炮
if(k) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]* (j+))%mod; //该行有一个炮的一列放一炮
if(j>) f[i][j][k]=(f[i][j][k]+f[i-][j-][k]* C(m-j+-k))%mod; //没有炮的两列各方一个炮
if(k>) f[i][j][k]=(f[i][j][k]+f[i-][j+][k-]* C(j+))%mod; //该行在有一个炮的两列各放一个炮
if(k) f[i][j][k]=(f[i][j][k]+f[i-][j][k-]* j*(m-j-k+))%mod; //该行在无炮的位置放一个炮,在有一个炮的一列再放一个跑
}
long long ans=;
for(int i=; i<=m; ++i)
for(int j=; i+j<=m; ++j)
ans+=f[n][i][j],ans%=mod;
printf("%lld\n",ans);
return ;
} int Aptal=Presist();
int main(){;}