洛谷P2051.中国象棋

题目大意

给定一个 \(n\times m(1\leq n,m\leq 100)\) 的棋盘，可以在棋盘中放入若干个炮（可以不放），求有多少种放置方案，使得棋盘上的所有炮不能相互攻击，答案对 \(9999973\) 取模。

思路

要使得所有的炮不能相互攻击，就必须使任意行，列上最多有 \(2\) 门炮，于是设 \(dp[i,j,k]\) 为放到了第 \(i\) 行，目前有 \(j\) 列上有 \(1\) 个炮， \(k\) 列上有 \(2\) 个炮的方案数。之后根据 \(6\) 种不同的情况分别进行转移即可。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
//#define int LL
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#pragma warning(disable :4996)
const double eps = 1e-8;
const LL mod = 9999973;
const LL MOD = 998244353;
const int maxn = 110;

LL N, M;
LL dp[maxn][maxn][maxn];

LL C2(LL x)
{
	return (x * (x - 1) / 2);
}

void solve()
{
	dp[1][0][0] = 1, dp[1][1][0] = M, dp[1][2][0] = C2(M);
	for (int i = 2; i <= N; i++)
	{
		for (int j = 0; j <= M; j++)
		{
			for (int k = 0; k <= M - j; k++)
			{
				dp[i][j][k] = dp[i - 1][j][k];
				if (j >= 1)
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k] * (M - (j - 1) - k) % mod) % mod;
				if (j >= 2)
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 2][k] * C2(M - (j - 2) - k) % mod) % mod;
				if (k >= 2)
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 2][k - 2] * C2(j + 2) % mod) % mod;
				if (k >= 1)
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j + 1][k - 1] * (j + 1) % mod) % mod;
				if (k >= 1)
					dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1] * j % mod * (M - j - (k - 1)) % mod) % mod;
			}

		}
	}
	LL ans = 0;
	for (int j = 0; j <= M; j++)
	{
		for (int k = 0; k <= M - j; k++)
			ans = (ans + dp[N][j][k]) % mod;
	}
	cout << ans << endl;
}

int main()
{
	IOS;
	cin >> N >> M;
	solve();

	return 0;
}