Solution [AHOI2009]中国象棋

题目大意:求在(n)行(m)列的棋盘上放置若干个炮使得它们互不攻击的方案数,对(9999973)取模

动态规划,计数

分析:没有炮互相攻击等价于没有三个炮在同一行/列

考虑用(f[i][m_1][m_2])表示前(i)行,有(m_1)列有一个炮,(m_2)列有两个炮的方案数

可以用刷表法降低思维难度

初始条件:

(f[1][0][0] = 1)

(f[1][1][0] = m)

(f[1][2][0] = C_m^2)

这个比较简单,转移可以大力分类讨论,即讨论第(i + 1)行的放置个数,以及放置方案

(1.i + 1)行放(0)个

(f[i + 1][m_1][m_2] += f[i][m_1][m_2])

(2.i + 1)行放(1)个,并且放在空列(有(0)个棋子的列)

(f[i + 1][m_1 + 1][m_2] += f[i][m_1][m_2] imes (m - m_1 - m_2))

(3.i + 1)行放(1)个,并且放在有(1)个棋子的列

(f[i + 1][m_1 - 1][m_2 + 1] += f[i][m_1][m_2] imes m_1)

(4.i + 1)行放(2)个,都放在空列

(f[i + 1][m_1 + 2][m_2] += f[i][m_1][m_2] imes C_{m-m_1-m_2}^2)

(5.i + 1)行放(2)个,一个放在空列,一个放在有(1)个棋子的列

(f[i + 1][m_1][m_2 + 1] += f[i][m_1][m_2] imes m_1 imes (m - m_1 - m_2))

(6.i + 1)行放(2)个,都放在有(1)个棋子的列

(f[i + 1][m_1 - 2][m_2 + 2] += f[i][m_1][m_2] imes C_{m_1}^2)

然后注意一下边界条件,避免非法状态和非法转移即可

#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 128,mod = 9999973;
int n,m;
ll f[maxn][maxn][maxn],ans;
inline ll C2(ll x){return x * (x - 1) / 2;}
int main(){
	scanf("%d %d",&n,&m);
	f[1][0][0] = 1;
	f[1][1][0] = m;
	f[1][2][0] = C2(m);
	for(int i = 1;i < n;i++)
		for(int m1 = 0;m1 <= m;m1++)
			for(int m2 = 0;m1 + m2 <= m;m2++){
				f[i + 1][m1][m2] += f[i][m1][m2],f[i + 1][m1][m2] %= mod;
				if(m1 + 1 <= m && m1 + m2 + 1 <= m)f[i + 1][m1 + 1][m2] += f[i][m1][m2] * ll(m - m1 - m2),f[i + 1][m1 + 1][m2] %= mod;
				if(m1 >= 1 && m2 < m)f[i + 1][m1 - 1][m2 + 1] += f[i][m1][m2] * (ll)m1,f[i + 1][m1 - 1][m2 + 1] %= mod;
				if(m1 + 2 <= m && m1 + m2 + 2 <= m)f[i + 1][m1 + 2][m2] += f[i][m1][m2] * C2(m - m1 - m2),f[i + 1][m1 + 2][m2] %= mod;
				if(m2 + 1 <= m && m1 + m2 + 1 <= m)f[i + 1][m1][m2 + 1] += f[i][m1][m2] * ll(m - m1 - m2) * m1,f[i + 1][m1][m2 + 1] %= mod;
				if(m1 >= 2 && m2 + 2 <= m)f[i + 1][m1 -  2][m2 + 2] += f[i][m1][m2] * C2(m1),f[i + 1][m1 - 2][m2 + 2] %= mod;
			}
	for(int m1 = 0;m1 <= m;m1++)
		for(int m2 = 0;m1 + m2 <= m;m2++)
			ans += f[n][m1][m2],ans %= mod;
	printf("%lld
",ans);
	return 0;
}