洛谷题面

妙题。

题目大意

在一个 \(n\) 行 \(m\) 列的棋盘上，让你放若干个炮（可以是 \(0\) 个），使得没有一个炮可以攻击到另一个炮，请问有多少种放置方法。

大家肯定很清楚，在中国象棋中炮的行走方式是：一个炮攻击到另一个炮，当且仅当它们在同一行或同一列中，且它们之间恰好有一个棋子。

方案数对 \(\textbf{9999973}\) 取模。

题目分析

令 \(dp[i,j,k]\) 表示放了前 \(i\) 行，有 \(j\) 列是有一个棋子，有 \(k\) 列是有 2 个棋子的合法方案数。

根据定义，初始化 \(dp[0,0,0]=1\)（显然是唯一可确定的），答案为 \(\sum\limits_{i=0}^m\sum\limits_{j=0}^mdp[n,i,j]\)。

来推一推式子，比较麻烦，特别是边界问题。

为了保证合法性，我们显然不会在已有两个棋子的列上再去添加任何棋子，所以状态转移是有限的。为方便，下面定义有一个棋子的列为“一棋列”，有两个棋子的列为“两棋列”，没有棋子的列为“无棋列”。

不选任何棋子时，直接继承上一状态，方程为 \(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j,k]\)。

放一个棋子时，有两种情况：

放在已有的“一棋列”里，少了一列“一棋列”，多了一列“两棋列”，也就是由 \(dp[i-1,j+1,k-1]\) 转移而来，由于是从上一个状态转移而来的，上一个转移状态的“一棋列”个数为 \(j+1\)，所以有 \(j+1\) 种选择。方程为 \(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j+1,k-1]\times (j+1)\)。

放在已有的“无棋列”里，多了一列“一棋列”，由 \(dp[i-1,j-1,k]\) 转移而来，上个状态的方案数为 \((m-(j-1)-k)\)（也就是“无棋列”的数量），方程为：\(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j-1,k]\times(m-(j-1)-k)\)。

放两个棋子时，有三种情况：

两个均放在“一棋列”，少了两个“一棋列”，多了两个“两棋列”，由 \(dp[i-1,j+2,k-2]\) 转移而来，上个状态的方案数为 \(C_{j+2}^2\)（也就是从“一棋列”中选两个），方程为：\(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j+2,k-2]\times C_{j+2}^2\)。

两个均放在“无棋列”，多了两个“一棋列”，由 \(dp[i-1,j-2,k]\) 转移而来，上个状态的方案数为 \(C_{m-(j-2)-k}^2\)（也就是从“无棋列”中选两个），方程为：\(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j+2,k-2]\times C_{m-(j-2)-k}^2\)。

一个放在“无棋列”，一个放在“一棋列”，多了一个“一棋列”又少了一个“一棋列”抵消了，多了一个“两棋列”，由 \(dp[i-1,j,k-1]\) 转移来，方案数为 \(j\times (m-j-(k-1))\)，方程为 \(dp[i,j,k]\gets dp[i,j,k]+dp[i-1,j,k-1]\times j\times(m-j-(k-1))\)。

其他就是些细节问题了，求组合的公式为：

如果直接暴力每次算的话很慢，如果把阶乘预处理出来的话你会发现会出现除法，而你又使用了 \(\bmod\)，所以要用逆元？不用那么麻烦，直接递推即可，\(C_{i}^j=C_{i-1}^j+C_{i-1}^{j-1}\)，虽然我知道只需要处理 \(j=2\) 的情况，但我还是全部预处理了出来（

注意开 long long。

本着精益求精的精神，我也写了一份逆元求组合数的代码（破罐子破摔再熬一会儿）：

inline void init() {
	fac[0] = 1;
	for (register int i = 1;i <= 100; ++ i) fac[i] = fac[i - 1] * i % mod;
}
inline int ksm(int x,int y,int p) {
    int res = 1;
    for (;y;y >>= 1ll) {
        if (y & 1ll) res = res * x % p;
        x = x * x % p;
    }
    return res % p;
}
inline int C(long long x,long long y) {
    int nx = ksm(fac[x - y],mod - 2,mod),ny = ksm(fac[y],mod - 2,mod);
    return MOD(MOD(fac[x] * nx) * ny);
}

代码

//2022/4/2
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include //need "INT_MAX","INT_MIN"
#include //need "memset"
#include 
#include 
#define int long long
#define enter putchar(10)
#define debug(c,que) cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) cout << arr[i] << w;
#define speed_up() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define Abs(x) ((x) > 0 ? (x) : -(x))
#define stop return(0)
const int mod = 9999973;
inline int MOD(int x) {
	if(x < 0) x += mod;
	return x % mod;
}
namespace Newstd {
	char buf[1 << 21],*p1 = buf,*p2 = buf;
	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
	}
	inline int read() {
		int ret = 0,f = 0;char ch = getc();
		while (!isdigit(ch)) {
			if(ch == '-') f = 1;
			ch = getc();
		}
		while (isdigit(ch)) {
			ret = (ret << 3) + (ret << 1) + ch - 48;
			ch = getc();
		}
		return f ? -ret : ret;
	}
	inline void write(int x) {
		if(x < 0) {
			putchar('-');
			x = -x;
		}
		if(x > 9) write(x / 10);
		putchar(x % 10 + '0');
	}
}
using namespace Newstd;
using namespace std;

const int N = 105;
int C[N][N],dp[N][N][N];
//dp[i][j][k]:放了前 i 行,有 j 列是有一个棋子,有 k 列是有 2 个棋子的合法方案数
int n,m;
inline void init() {
	C[0][0] = 1;
	for (register int i = 1;i <= 100; ++ i) {
		C[i][0] = 1;
		for (register int j = 1;j <= i; ++ j) {
			C[i][j] = MOD(C[i - 1][j] + C[i - 1][j - 1]);
		}
	}
}
#undef int
int main(void) {
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	#define int long long
	init();
	n = read(),m = read();
	dp[0][0][0] = 1;
	for (register int i = 1;i <= n; ++ i) {
		for (register int j = 0;j <= m; ++ j) {//枚举一个棋子的列数
			for (register int k = 0;k <= m - j; ++ k) {//枚举两个棋子的列数
				dp[i][j][k] = dp[i - 1][j][k];//不选
				//放一个棋子
				if (k >= 1) dp[i][j][k] = MOD(dp[i][j][k] + dp[i - 1][j + 1][k - 1] * (j + 1));//放在一个棋子的列,现在变成两个棋子
				if (j >= 1) dp[i][j][k] = MOD(dp[i][j][k] + dp[i - 1][j - 1][k] * (m - (j - 1) - k));//放在没有棋子的列,现在变成一个棋子
				//放两个棋子
				if (k >= 1) dp[i][j][k] = MOD(dp[i][j][k] + dp[i - 1][j][k - 1] * j * (m - j - (k - 1)));//一个放在有一个棋子的列,一个放在没有棋子的列
				if (j >= 2) dp[i][j][k] = MOD(dp[i][j][k] + dp[i - 1][j - 2][k] * C[m - (j - 2) - k][2]);//两个都放在没有棋子的列
				if (k >= 2) dp[i][j][k] = MOD(dp[i][j][k] + dp[i - 1][j + 2][k - 2] * C[j + 2][2]);//两个都放在一个格子的列
			}
		}
	}
	int ans = 0;
	for (register int i = 0;i <= m; ++ i) {
		for (register int j = 0;j <= m; ++ j) {
			ans = MOD(ans + dp[n][i][j]);
		}
	}
	printf("%lld\n",ans);

	return 0;
}