description
在 N 行 M 列的棋盘上, 放若干个炮可以是 0 个, 使得没有任何一个炮可以攻击另一个炮. 请问有多少种放置方法? 中国象棋中炮的行走方式大家应该很清楚吧.
analysis
\(DP\), 容易知道每行至多有两个炮, 否则会互相打到
设 \(f[i][j][k]\) 表示到放到第 \(i\) 行, 有 \(j\) 列放了一个炮,\(k\) 列放了两个炮的方案数
该行不放炮, 则直接继承上一行的答案
\[f[i][j][k]+=f[i-1][j][k]\]
一个炮放在没有炮的列上, 一个炮的列数 \(+1\), 且有 \(m-k-(j-1)\) 个没有炮的列可以放
\[f[i][j][k]+=f[i-1][j-1][k]*[m-k-(j-1)]\]
一个炮放在一个炮的列上, 一个炮的列数 \(-1\), 两个炮的列数 \(+1\), 且有 \(j+1\) 个一个炮的列可以放
\[f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)\]
一个炮放在一个炮的列上, 一个炮放在没有炮的列上, 两个炮的列数 \(+1\), 且分别有 \(j\) 列,\(m-(k-1)-j\) 列可以放
\[f[i][j][k]+=f[i-1][j][k-1]*j*[m-(k-1)-j]\]
两个炮放在没有炮的列上, 一个炮的列数 \(+2\), 且有 \(C^{2}_{m-(j-2)-k}\) 种方案
\[f[i][j][k]+=f[i-1][j-2][k]*C^{2}_{m-(j-2)-k}\]
两个炮放在一个炮的列上, 一个炮的列数 \(-2\), 两个炮的列数 \(+2\), 且有 \(C^{2}_{j+2}\) 种方案
\[f[i][j][k]+=f[i-1][j+2][k-2]*C^{2}_{j+2}\]
如此转移即可, 注意判断边界
- code
- #pragma GCC optimize("O3")
- #pragma G++ optimize("O3")
- #include
- #include
- #include
- #define MAXN 105
- #define ha 9999973
- #define ll long long
- #define reg register ll
- #define fo(i,a,b) for (reg i=a;i<=b;++i)
- #define fd(i,a,b) for (reg i=a;i>=b;--i)
- using namespace std;
- ll f[MAXN][MAXN][MAXN];
- ll c[MAXN][MAXN];
- ll n,m,ans;
- inline ll read()
- {
- ll x=0,f=1;char ch=getchar();
- while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
- while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
- return x*f;
- }
- inline ll C(ll n){return n*(n-1)/2;}
- int main()
- {
- n=read(),m=read(),f[0][0][0]=1;
- fo(i,1,n)
- {
- fo(j,0,m)
- {
- fo(k,0,m-j)
- {
- f[i][j][k]=f[i-1][j][k];// 不填
- if (k-1>=0)
- (f[i][j][k]+=f[i-1][j+1][k-1]*(j+1)%ha)%=ha;// 一颗填一个炮的列
- if (j-1>=0)
- (f[i][j][k]+=f[i-1][j-1][k]*(m-(j-1)-k))%=ha;// 一颗填没有炮的列
- if (k-1>=0)
- (f[i][j][k]+=f[i-1][j][k-1]*j%ha*(m-j-(k-1)))%=ha;// 一颗填一个炮的列, 一颗填没有炮的列
- if (j-2>=0)
- (f[i][j][k]+=f[i-1][j-2][k]*C(m-(j-2)-k))%=ha;// 两颗填没有炮的列
- if (k-2>=0)
- (f[i][j][k]+=f[i-1][j+2][k-2]*C(j+2))%=ha;// 两颗填一个炮的列
- }
- }
- }
- fo(i,0,m)fo(j,0,m-i)(ans+=f[n][i][j])%=ha;
- printf("%lld\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3201860.html