看见第一眼觉得是状压 \(\text{DP}\)? 观察数据范围发现不可做
那按照最常规思路设状态试试?
设状态为 \(dp[i][j]\) 表示 \(i*j\) 的棋盘的方案数
好像转移不了欸 要不再来一维?
\(dp[i][j][k]\) 表示... 还是不行啊
要求的就是每行, 每列都不能有三个及其以上的炮
所以一共就只有三种状态: 没有, 一个炮, 两个炮
但是列与列之间交换位置是完全没有问题的
所以设状态为 \(dp[i][j][k]\) 做了 \(i\) 行, 有 \(j\) 列放了一个炮, 有 \(k\) 列放了两个炮
如果第 \(i\) 行不放, 则有
\[ dp[i][j][k]+=dp[i-1][j][k] \]
放一个, 则上一个状态一定是 \(dp[i-1][j-1][k]\) 或者是 \(dp[i-1][j+1][k-1]\), 由简单组合数学可得
\[ dp[i][j][k]+=(m-k-(j-1))\cdot dp[i-1][j-1][k]+(j+1) \cdot dp[i-1][j+1][k-1] \]
放两个, 那一定从 \(dp[i-1][j][k-1]\) 或者 \(dp[i-1][j-2][k]\) 或者 \(dp[i-1][j+2][k-2]\) 转移而来
则有 (自己推式子感觉真好)
\[ dp[i][j][k]+=(m-j-(k-1)) \cdot j\cdot dp[i-1][j][k-1]\dp[i][j][k]+={C}_{m-k-(j-2)}^{2} \cdot dp[i-1][j-2][k]\dp[i][j][k]+={C}_{j+2}^{2}*dp[i-1][j+2][k-2]\\]
然后就是处理边界问题了
估计要开 \(long\ long\)(狗头
贴代码
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll p=9999973;
- const ll maxn=1e2+10;
- ll n,m,dp[maxn][maxn][maxn];
- ll C(ll num)
- {
- return num*(num-1)/2;
- }
- int main()
- {
- scanf("%lld%lld",&n,&m);
- dp[0][0][0]=1;
- for(int i=1;i<=n;++i)
- for(int j=0;j<=m;++j)
- for(int k=0;j+k<=m;++k)
- {
- if(i-1>=0) dp[i][j][k]+=dp[i-1][j][k];
- if(k-1>=0) dp[i][j][k]+=(j+1)*dp[i-1][j+1][k-1];
- if(j-1>=0) dp[i][j][k]+=(m-k-(j-1))*dp[i-1][j-1][k];
- if(k-2>=0) dp[i][j][k]+=C(j+2)*dp[i-1][j+2][k-2];
- if(k-1>=0) dp[i][j][k]+=(m-j-(k-1))*j*dp[i-1][j][k-1];
- if(j-2>=0) dp[i][j][k]+=C(m-k-(j-2))*dp[i-1][j-2][k];
- dp[i][j][k]%=p;
- }
- ll ans=0;
- for(int i=0;i<=m;++i)
- for(int j=0;i+j<=m;++j)
- ans=(ans+dp[n][i][j])%p;
- printf("%lld\n",(ans+p)%p);
- return 0;
- }
- \(\text{End.}\)
来源: http://www.bubuko.com/infodetail-3131337.html