題目鏈接

題意概述：n行m列棋盤放若干個棋子每行每列最多兩個求方案總數，答案對9999973取模。

可以比較容易看出這是個dp，設f[i][j][k]表示前i行j列放1個棋子k列放2個棋子的方案總數。轉移時分類討論+計數就好了。分類討論比較麻煩需要仔細考慮一下。

吐槽：我把循環里的m寫成n還有50，查了半天（真的半天）取模QAQ

#include<cstring> #include<iostream> #include<cctype> #include<cstdio> #include<algorithm> #define now f[i][j][k] #define ll unsigned long long using namespace std; inline int read() {register int X=0;register char ch=0;bool flag=0;for(; !isdigit(ch); ch=getchar()) if(ch=='-') flag=1;for(; isdigit(ch); ch=getchar()) X=(X<<3)+(X<<1)+ch-'0';return (flag ? -X : X); } int N=101; const ll mod=9999973; int n,m; ll f[201][201][201],ans; int C(int x) {return x*(x-1)/2; } int main() {n=read(),m=read(),f[0][0][0]=1;for(int i=0;i<n;i++)for(int j=0;j<=m;j++)for(int k=0;k+j<=m;k++){if(now){(f[i+1][j][k]+=now)%=mod;if(m-j-k > 0) (f[i+1][j+1][k]+=now*(m-j-k))%=mod;if(j > 0) (f[i+1][j-1][k+1]+=now*j)%=mod;if(m-j-k > 1) (f[i+1][j+2][k]+=now*(C(m-j-k)%mod))%=mod;if(j > 0 && m-j-k > 0) (f[i+1][j][k+1]+=now*j%mod*(m-j-k))%=mod;if(j > 1) (f[i+1][j-2][k+2]+=now*(C(j)%mod))%=mod;}}for(int i=0; i<=m; i++)for(int j=0; j+i<=m; j++)(ans+=f[n][i][j])%=mod;printf("%llu\n",ans); }

?

?

轉載于:https://www.cnblogs.com/mordor/p/9578758.html

總結

以上是生活随笔為你收集整理的洛谷2051 [AHOI2009]中国象棋的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。