首页 > 代码库 > bzoj1801 [Ahoi2009]chess 中国象棋
bzoj1801 [Ahoi2009]chess 中国象棋
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
显然问题就是一行一列最多只能放两个棋子，求方案数
dp:f[i][j][k]表示前i行已经有j列有一个棋子，k列有两个棋子的方案数
那么第i行可以不放棋子、放一个棋子、放两个棋子。
其中，棋子可以放在原来没有棋子的某一列上，也可以放在已经有一个棋子的某一列上。但是已经有两个棋子的列上是不能放的。
然后要分6种情况讨论下。这里想法其实不难，但是容易乱……我还wa了一次
1、不放
2、一个棋子，放在原来没棋子的某一列上
3、一个棋子，放在原来有一个棋子的某一列上
4、两个棋子，一个在原来没棋子的列上，一个在原来一个棋子的列上
5、两个棋子，都放在原来没棋子的列上
6、两个棋子，都放在原来一个棋子的列上
#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#include<cmath>#include<queue>#include<deque>#include<set>#include<map>#include<ctime>#define LL long long#define inf 0x7ffffff#define pa pair<int,int>#define mod 9999973using namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void write(LL a){ if (a<0){printf("-");a=-a;} if (a>=10)write(a/10); putchar(a%10+‘0‘);}inline void writeln(LL a){write(a);printf("\n");}LL f[110][110][110];int n,m;LL ans;inline LL calc(LL x){return x*(x-1)/2;}int main(){ n=read();m=read(); f[0][0][0]=1; for (int i=1;i<=n;i++) for (int j=0;j<=m;j++) for (int k=0;k<=m-j;k++) { f[i][j][k]=f[i-1][j][k];//(1) if (j)f[i][j][k]+=f[i-1][j-1][k]*(m-k-j+1);//(2) if (j<m&&k)f[i][j][k]+=f[i-1][j+1][k-1]*(j+1);//(3) if (j&&k)f[i][j][k]+=f[i-1][j][k-1]*j*(m-j-k+1);//(4) if (j>1)f[i][j][k]+=f[i-1][j-2][k]*calc(m-k-j+2);//(5) if (j<=m-2&&k>1)f[i][j][k]+=f[i-1][j+2][k-2]*calc(j+2);//(6) f[i][j][k]%=mod; } for (int i=0;i<=m;i++) for (int j=0;j<=m-i;j++) ans=(ans+f[n][i][j])%mod; printf("%lld\n",ans);}
bzoj1801 [Ahoi2009]chess 中国象棋
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。