【AHOI2009】中国象棋

经过不懈的努力终于自己想出来了，感动 原题： 这次小可可想解决的难题和中国象棋有关，在一个N行M列的棋盘上，让你放若干个炮（可以是0个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好 有一个棋子。你也来和小可可一起锻炼一下思维吧！ N和M均不超过100 首先这题标的tag是DP，但是实际上应该是计数题，算是递推吧 和楼下mjl（stdcall）相反，这题我好像想了挺久的T_T 首先需要看出来问题的实质是给一个棋盘，每行每列最多放2个棋子求方案数 最开始我想的是安格处理，但是发现如果有两个棋子的话状态能储存的信息极少，统计答案非常困难 再次注意题目中的特殊性： 最重要的，因为这题要求的是计数，所以每个格子放在那里是不用管的，我们关心的就是方案数 第二个性质，因为每行每列上限2，所以如果将状态设为每一行里n个格子中，所在列上放了1个，0个的格子有多少个，就可以很方便地用数组表示出来 这个状态的设计我一开始就有了想法，但是没有注意到第一条的性质，认为最后统计答案会比较麻烦所以放弃了 再次注意，棋子怎么放是无所谓的，所有的情况都变成了方案数储存在数组里 这种状态相比状压，优势就在于丢掉了“每个棋子放在那里”这样一个无用的信息，而只关注我们需要的，对于每一种状态，它的方案数是多少 因为这样设计状态涵盖了所有情况，所以正确性是有保证的 （好像越描越黑了。。。。。。 总之明确了状态的设计之后，写出递推式就很容易了 对于每一行，可以不放棋子，放一个或到所在列有0个棋子的格子上，放一个或到所在列有1个棋子的格子上，两个所在列分别有1个棋子和0个棋子的格子各放一个 注意还要乘上能放的位置数，Talk is cheap, show you the code： $$ f[i][j][k]=f[i-1][j][k]+(j+1)*f[i-1][j+1][k]+(k+1)*f[i-1][j-1][k+1]+(j+2)*(j+1)/2*f[i-1][j+2][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2]+(j)*(k+1)*f[i-1][j][k+1] $$ （有点长…… 写出递推式之后就好办了，实现起来比较容易 没有需要注意的坑，把式子实现出来就能过了 我也1A了！（开心 代码： ```cpp //去掉了头文件 #define ll long long const int mo=9999973; int n,m; // 1个 0个 ll f[110][110][110]; //f[i][j][k]=f[i-1][j][k]+(j+1)*f[i-1][j+1][k]+(k+1)*f[i-1][j-1][k+1] // +(j+2)*(j+1)/2*f[i-1][j+2][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2] // +(j)*(k+1)*f[i-1][j][k+1] int main(){freopen("ddd.in","r",stdin); memset(f,0,sizeof(f)); cin>>n>>m; if(m>n) swap(n,m); f[0][0][m]=1; for(int i=1;i<=n;++i)for(int j=0;j<=m;++j)for(int k=0;k<=m;++k){ f[i][j][k]=f[i-1][j][k]; if(j+1<=m) f[i][j][k]=(f[i][j][k]+(j+1)*f[i-1][j+1][k])%mo; if(k+1<=m && j-1>=0) f[i][j][k]=(f[i][j][k]+(k+1)*f[i-1][j-1][k+1])%mo; if(j+2<=m) f[i][j][k]=(f[i][j][k]+(j+2)*(j+1)/2*f[i-1][j+2][k])%mo; if(k+2<=m && j-2>=0) f[i][j][k]=(f[i][j][k]+(k+2)*(k+1)/2*f[i-1][j-2][k+2])%mo; if(k+1<=m) f[i][j][k]=(f[i][j][k]+(j)*(k+1)*f[i-1][j][k+1])%mo; } ll ans=0; for(int i=0;i<=m;++i)for(int j=0;j<=m;++j) ans=(ans+f[n][i][j])%mo; cout<<ans<<endl; return 0; } ```