注意到一行只能放012個炮，我們只需要知道列的狀態(tài)，不用狀壓行
所以設(shè)f[i][j][k]表示前i行有j列有1個炮，有k列有2個炮的方案數(shù)
然后分情況討論轉(zhuǎn)移就行了

#include<cstdio> #include<iostream> using namespace std; const int N=105,mod=9999973; long long n,m,f[N][N][N],ans; int main() {scanf("%lld%lld",&n,&m);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];if(j>=1)f[i][j][k]=(f[i][j][k]+(f[i-1][j-1][k]*(m-j+1ll-k))%mod)%mod;if(k>=1&&j+1<=m)f[i][j][k]=(f[i][j][k]+(f[i-1][j+1][k-1]*(j+1ll))%mod)%mod;if(j>=2)f[i][j][k]=(f[i][j][k]+(f[i-1][j-2][k]*((m-j+2ll-k)*(m-j+1ll-k)/2)%mod)%mod)%mod;if(k>=2&&j+2<=m)f[i][j][k]=(f[i][j][k]+(f[i-1][j+2][k-2]*((long long)(j+2ll)*(long long)(j+1ll)/2)%mod)%mod)%mod;if(j>=1&&k>=1)f[i][j][k]=(f[i][j][k]+(f[i-1][j][k-1]*(long long)j%mod*(m-j-k+1)%mod)%mod)%mod;if(i==n)ans=(ans+f[i][j][k])%mod;}printf("%lld\n",ans);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/lokiii/p/9368864.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的bzoj 1801: [Ahoi2009]chess 中国象棋【dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。