引言
本文视频版传送门
视频封面：
最近广东一模的压轴题竟然考二维dp！考的还是oier耳熟能详的国际象棋棋盘放“车”的模型！这期视频我们先讲广东一模的两种解法，然后扩展到洛谷P1350的两种解法。Hans还会额外给大家送上一道类似的自编算法题喔！又是OIER最喜欢的一集，一起来领略动态规划和组合数学的魅力！
题干：
甲社区有 $n$ 个女生和 $n$ 个男生，且每个女生都认识所有男生；乙社区有 $n$ 个女生 $g_1, g_2, \cdots, g_n$ 和 $2n-1$ 个男生 $b_1, b_2, \cdots, b_{2n-1}$ ，其中女生 $g_i (i=1,2,\cdots,n)$ 认识男生 $b_j (j=1,2,\cdots,2i-1)$ ，但不认识其他男生。现从甲社区和乙社区分别选出 $m (m=1,2,\cdots,n)$ 队选手参加社区比赛，每队选手均为2人
(1) 若 $n=3, m=1$ ，求所有参赛队伍的参赛选手性别相同的概率
(2) 若要求每队选手必须是男、女组队，且女生认识男生，分别记甲社区和乙社区选出的 $m$ 队的不同选法种数为 $A_n(m)$ 和 $B_n(m)$
-
(i) 求 $A_n(m)$ ，并证明：当 $2 \leq m \leq n-1$ 时， $A_n(m) = A_{n-1}(m) + (2n-m)A_{n-1}(m-1)$ 三者之间的递推公式，并说明理由；（注：题干可能是命题人赶工出来的，语句不通顺。意思是让我们证明A数组满足这个递推式）
-
(ii) 若乙社区将选出的 $m$ 个男生和 $m$ 个女生按男、女搭配随机组队，求组队结果满足参赛要求的概率
本文 52pojie： https://www.52pojie.cn/thread-2103232-1-1.html
本文 博客园： https://www.cnblogs.com/hans77/articles/19874256
本文 juejin： https://juejin.cn/post/7628898648117985299
作者：hans774882968以及hans774882968以及hans774882968以及hans77
（1）送分
记事件 $A_{1},\ A_{2},\ B_{1},\ B_{2}$ 分别表示甲社区参赛选手都是女生、甲社区参赛选手都是男生、乙社区参赛选手都是女生、乙社区参赛选手都是男生。则分别考虑4种情况得：
$$
\begin{cases}
P(A_{1})=P(A_{2})=\frac{C_{3}^2}{C_{6}^2}=\frac{1}{5} \\
P(B_{1})=\frac{C_{3}^2}{C_{8}^2}=\frac{3}{28} \\
P(B_{2})=\frac{C_{5}^2}{C_{8}^2}=\frac{5}{14}
\end{cases}
$$
所求事件概率 $P=P(A_{1})P(B_{1})+P(A_{2})P(B_{2})=\frac{13}{140}$
送分题要格外注意细节和规范！
（2）证明 $A_n(m) = A_{n-1}(m) + (2n-m)A_{n-1}(m-1)$
因为甲社区是每个女生都认识所有男生，呈现一种高度对称性，所以我们可以大胆猜测：这里直接算方案数会更简单。
法1：直接算反而更简单
我们考虑3步走：
- 找m个女生，方案数 $C_{n}^m$
- 找m个男生，方案数 $C_{n}^m$
- m男m女随机两两组队。不妨男女都从1到m编号，于是我们只需要为1到m号女生各确定一个男生编号。方案数就是排列数 $m!$
综上， $A_{n}(m)=(C_{n}^m)^2 \cdot m! = \frac{(n!)^2}{((n-m)!)^2m!}$ 。最后验证递推式就很简单了：
$$
\begin{align}
rhs&=\frac{((n-1)!)^2}{((n-1-m)!)^2m!}+(2n-m)\frac{((n-1)!)^2}{((n-m)!)^2(m-1)!} \\
&=\frac{((n-1)!)^2}{((n-1-m)!)^2(m-1)!}(\frac{1}{m}+(2n-m)\frac{1}{(n-m)^2}) \\
&=\frac{((n-1)!)^2}{((n-1-m)!)^2(m-1)!} \cdot \frac{n^2}{(n-m)^2m} \\
&=\frac{(n!)^2}{((n-m)!)^2m!}=lhs
\end{align}
$$
法2：求递推式看似多此一举，却能给（3）启发
第二问还有一种更为复杂的做法。这里为什么要讲这种做法呢？不是多此一举吗？因为这里体现的分类讨论思想会给下一问和后面的拓展启发。
首先，我们从解读A的语义入手。 $A_{n-1}(m)$ 表示少了男生 $b_{n}$ 和女生 $g_{n}$ ，但还是有m队。 $A_{n-1}(m-1)$ 表示少了男生 $b_{n}$ 和女生 $g_{n}$ ，但少了一队。这启发我们：
考虑对男生 $b_{n}$ 和女生 $g_{n}$ 是否参加社区比赛分类讨论，共2*2=4种情况
- $b_{n},\ g_{n}$ 都不参加。那么其他2n-2人已经组成m队，方案数 $A_{n-1}(m)$
- $b_{n}$ 参加， $g_{n}$ 不参加。首先其他2n-2人组成m-1队（ $A_{n-1}(m-1)$ ）。此时女生还有n-m+1人没被选中，但记得排除 $g_{n}$ ，于是 $b_{n}$ 可挑选组队的女生数为 $n-m$ 。总方案数 $(n-m)A_{n-1}(m-1)$
- $g_{n}$ 参加， $b_{n}$ 不参加。和“2”类似，不赘述。
- $b_{n},\ g_{n}$ 都参加。首先其他2n-2人组成m-1队（ $A_{n-1}(m-1)$ ）。接下来是易错点：不要默认 $b_{n},\ g_{n}$ 在同一队。实际上 $g_{n}$ 可以选择拆散一个组好的队伍，从而和其他参赛男生组队。总方案数 $mA_{n-1}(m-1)$
综上，得递推式 $A_n(m) = A_{n-1}(m) + (2(n-m)+m)A_{n-1}(m-1) = A_{n-1}(m) + (2n-m)A_{n-1}(m-1)$
（3）直接写出通项公式，碰壁
随机组队的总方案数是 $C_{n}^mC_{2n-1}^m m!$ ，所求概率 $P=\frac{B_{n}(m)}{C_{n}^mC_{2n-1}^m m!}$ 。所以我们需要求 $B_{n}(m)$ 的通项公式。
[!note] 想法
先试试直接用组合意义写出通项公式。碰壁了就考虑子问题的性质，先求递推式再求通项！
考虑枚举被选中的女生编号 $g_{i_{1}},\ g_{i_{2}},\ \dots,\ g_{i_{m}}$ （共 $C_{n}^m$ 种情况）。不失一般性，约定 $1 \leq g_{i_{1}} \lt g_{i_{2}} \lt \dots \lt g_{i_{m}} \leq n$ 。考虑第k个被选中的女生 $g_{i_{k}}$ ，则她可选的男生数为 $(2i_{k}-1)-(k-1)=2i_{k}-k$ 。故：
$$
B_{n}(m)=\sum_{1 \leq g_{i_{1}} \lt g_{i_{2}} \lt \dots \lt g_{i_{m}} \leq n} \prod_{k=1}^m (2i_{k}-k)
$$
化简这条式子似乎不容易，我们还是考虑从B的递推式入手吧！
（3）意外发现B和A是完全一样的数组！
模仿上一问的法2来分类讨论。但因为只有 $g_{n}$ 认识 $b_{2n-2},\ b_{2n-1}$ ，所以我们只按 $g_{n}$ 是否参赛来分类：
- $g_{n}$ 不参赛。 $B_{n-1}(m)$
- $g_{n}$ 参赛。首先其他3n-3人组成m-1队（ $B_{n-1}(m-1)$ ）。这里 $g_{n}$ 不能拆散组好的队伍，所以需要在没被选中的 $(2n-1)-(m-1)=2n-m$ 位男生中选一位组队。总方案数 $(2n-m)B_{n-1}(m-1)$
综上，得到递推式
$$
B_n(m) = B_{n-1}(m) + (2n-m)B_{n-1}(m-1)
$$
诶，B的递推式刚好和A一样！
$$
A_n(m) = A_{n-1}(m) + (2n-m)A_{n-1}(m-1)
$$
这说明A和B相等！
（3）收尾
不要高兴得太早！要记得检查边界情况！ $A_{n}(1)=n^2,\ B_{n}(1)=1+3+\dots+(2n-1)=n^2=A_{n}(1)$ ，确实一样，放心了！
注：如果你打算法竞赛，你就会知道 $n \geq 1,\ m=0$ 可以直接约定A和B数组都为1，于是不需要验算 $B_{n}(1)$
所以所求概率
$$
P=\frac{B_{n}(m)}{C_{n}^mC_{2n-1}^m m!}=\frac{(C_{n}^m)^2 \cdot m!}{C_{n}^mC_{2n-1}^m m!}=\frac{C_{n}^m}{C_{2n-1}^m}=\frac{n!(2n-1-m)!}{(n-m)!(2n-1)!}
$$
（3）回顾通项公式，看看有没有能力化简它
我们之前已经求出：
$$
B_{n}(m)=\sum_{1 \leq g_{i_{1}} \lt g_{i_{2}} \lt \dots \lt g_{i_{m}} \leq n} \prod_{k=1}^m (2i_{k}-k)
$$
而刚刚我们也领悟了 $B_{n}(m)$ 的组合意义。于是我们不难想到如何拆分这个式子：把这 $C_{n}^m$ 项分为 $i_{m} \lt n$ 和 $i_{m} = n$ 两类。
- $i_{m} \lt n$ ：就是 $B_{n-1}(m)$
- $i_{m} = n$ ：把 $2i_{m}-m=2n-m$ 这个公因子提出来，就得到 $(2n-m)B_{n-1}(m-1)$ （懒得把式子写完整了）
如果你注意力惊人，想到通项公式转递推式，就能在不知道组合意义的情况下解决这题
进一步深挖： $A_{n}(m)$ 究竟是什么？
在OEIS输入1, 64, 1568, 18816, 117600, 376320, 564480, 322560, 40320这个数列，就得到以下组合意义：
- T(n,k) is the number of increasing subsequences of length n-k over all permutations of
[n]
- T(n,k) is also the number of ways to place k nonattacking rooks on an n X n chessboard
1：选择n-k个数的方案数 $C_{n}^{n-k}$ ，为n-k个数选n-k个位置的方案数 $C_{n}^{n-k}$ 。剩下k个数可以任意排，方案数 $k!$
2：引入模型1：把m个车放到 $n \times n$ 的棋盘上，要求任意两个车不能在同一行，也不能在同一列，求方案数。不难发现，前面第二问等价于模型1：有车的行可以认为是被选中的男生，有车的列可以认为是被选中的女生。
视角1：通项公式
- 选择m行和m列放车。方案数 $C_{n}^m \cdot C_{n}^m$
- 问题转化为同一问题的特殊情况：求m个车放到 $m \times m$ 的棋盘上的方案数。第一行有m种放法，第二行有m-1种，……，第m行有1种。总方案数 $m!$
综上，总方案数 $(C_{n}^m)^2 \cdot m!$
视角2：前面第二问的递推式 $A_n(m) = A_{n-1}(m) + (2n-m)A_{n-1}(m-1)$
设dp[i,j]表示在i*i的棋盘上放j个车的方案数。边界条件：答案为dp[n,m]，dp[i,0]=1。模仿前面第二问的法2来分类讨论：
dp[i-1,j]表示j个车都放在(i-1)*(i-1)的棋盘上- 第i行放一个车，但第i列不放车（对应前面 $b_{i}$ 参赛 $g_{i}$ 不参赛），则 $(i,i)$ 位置不能放车。方案数 $((i-1)-(j-1))dp[i-1,j-1]=(i-j)dp[i-1,j-1]$
- 第i列放一个车，但第i行不放车。同上，方案数 $(i-j)dp[i-1,j-1]$
- 第i行第i列都放车。类似地，拆散组队的操作，对应这里挪之前放好的棋子的动作。设被挪动的棋子是 $(x,y)\ (1 \leq x,y \leq i-1)$ ，则 $g_{i}$ 和 $b_{x}$ 组队， $b_{i}$ 和 $g_{y}$ 组队，对应第j个棋子被放到 $(i,y)$ ，被挪动的棋子被放到 $(x,i)$ 。挪棋子的方案数j-1，加上第j个棋子就放在 $(i,i)$ 的1个方案，得 $jdp[i-1,j-1]$
综上，成功得到和第二问一样的递推式 $dp[i,j]=dp[i-1,j]+(2i-j)dp[i-1,j-1]$
视角3：另一种动态规划（普适性更强）
设dp[i,j]表示棋盘前i行上放j个车的方案数，则：
- 边界条件：答案为
dp[n,m]，dp[i,0]=1
- 仍然按第j个车放的位置分类讨论：
dp[i-1,j]表示j个车都放在前i-1行，第i行没有车dp[i-1,j-1]表示第j个车要放在第i行。第i行有n个格子，但已经有j-1个被占用，所以有n-j+1个格子可选
所以状态转移方程：
$$
dp[i,j]=dp[i-1,j]+(n-j+1)dp[i-1,j-1]
$$
相比于视角2，视角3的dp定义的普适性更强，因为它适用于任意形状的棋盘。
前面第三问等价于特定形状的棋盘放车的方案数
类似地，前面的第三问等价于这个问题：有以下形状的棋盘
x 1列
xxx 3列
...
xxxxxxx 2n-1列
把m个车放到这个棋盘上，要求任意两个车不能在同一行，也不能在同一列，求方案数。
模仿刚刚说的视角3，设dp[i,j]表示棋盘前i行放j个车的方案数，则：
dp[i-1,j]表示j个车都放在前i-1行，第i行没有车dp[i-1,j-1]表示第j个车要放在第i行。第i行有 $2i-1$ 个格子，但已经有j-1个被占用，所以有 $(2i-1)-(j-1)=2i-j$ 个格子可选
所以状态转移方程：
$$
dp[i,j]=dp[i-1,j]+(2i-j)dp[i-1,j-1]
$$
前面第三问之所以能求出和第二问一样的递推式，是因为第二问采用了视角2的dp定义，第三问采用了视角3的dp定义！妙哉！
扩展2：我自编的一道水题
我们发现视角3介绍的dp对于任意形状的棋盘都适用。所以不妨来做做下面这题：棋盘有2n行，第2k+1、2k+2行（k从0到n-1）的格子数是3k+2（每一行的格子数：2、2、5、5、8、8……）。试求放m个车的方案数
只需要把之前视角3的状态转移方程的系数，改成代码里的get_width函数
def compute_dp(n, m_max=None):
"""
计算升级版棋盘的dp[i][j]
dp[i][j] = 前i行放置j个非进攻型车的方案数
第2k+1行和第2k+2行各有3k+2个可放置列
"""
rows = 2 * n
if m_max is None:
m_max = rows
dp = [[0] * (m_max + 1) for _ in range(rows + 1)]
for i in range(rows + 1):
dp[i][0] = 1
def get_width(row):
"""第row行的可放置列数（row从1开始）"""
k = (row - 1) // 2
return 3 * k + 2
for i in range(1, rows + 1):
width_i = get_width(i)
for j in range(1, min(i, m_max) + 1):
# 递推式：
# 1. 第i行不放车：dp[i-1][j]
# 2. 第i行放车：(width_i - (j-1)) * dp[i-1][j-1]
if width_i >= j:
dp[i][j] = dp[i - 1][j] + (width_i - j + 1) * dp[i - 1][j - 1]
else:
dp[i][j] = dp[i - 1][j]
return dp
扩展3：洛谷P1350
洛谷P1350题干传送门
有这样一个网格棋盘，$a,b,c,d$ 表示对应边长度，也就是对应的格子数：
当 $a=b=c=d=2$ 时，对应这样一个棋盘：
要在这个棋盘上放 $k$ 个相互不攻击的车，也就是这 $k$ 个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。
输入五个非负整数 $0\leq a,b,c,d,k\leq 10^3$ ，且至少有一种可行方案。答案要 $\bmod$ $10^5+3$
法1：扩展模型1求通项公式
首先，我们把模型1扩展到n*m棋盘的情况（模型2）：把k个车放到 $n \times m$ 的棋盘上，要求任意两个车不能在同一行，也不能在同一列，求方案数
同模型1，方案数是 $C_{n}^k \cdot C_{m}^k \cdot k!$ 。 $C_{n}^k \cdot C_{m}^k$ 表示把问题转化为求k个车放到 $k \times k$ 的棋盘上的方案数
棋盘可以看成由两个矩形组成，所以我们可以有两个想法：
- 先在
c*d的矩形上放车，再在a*(b+d)的矩形上放车
- 先在
a*b的矩形上放车，再在(a+c)*d的矩形上放车
1，设在c*d的矩形上放了i个车（ $0 \leq i \leq k$ ）。因为a*(b+d)的矩形有i行被占用了，所以相当于矩形变成了a*(b+d-i)。套模型2的公式得总方案数：
$$
\sum_{i=0}^{k} C_{c}^iC_{d}^ii! \cdot C_{a}^{k-i}C_{b+d-i}^{k-i}(k-i)!
$$
2，设在a*b的矩形上放了i个车（ $0 \leq i \leq k$ ）。因为(a+c)*d的矩形有i列被占用了，所以相当于矩形变成了(a+c-i)*d。套模型2的公式得总方案数：
$$
\sum_{i=0}^{k} C_{a}^iC_{b}^ii! \cdot C_{d}^{k-i}C_{a+c-i}^{k-i}(k-i)!
$$
MOD = 100003
MAX_N = 2005
C = [[0] * MAX_N for _ in range(MAX_N)]
fact = [1] * MAX_N
def precompute():
for i in range(MAX_N):
C[i][0] = 1
for j in range(1, i + 1):
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD
for i in range(1, MAX_N):
fact[i] = (fact[i - 1] * i) % MOD
def solve_expr1(a, b, c, d, k):
"""
计算表达式 1:
sum_{i=0}^{k} C(c, i) * C(d, i) * i! * C(a, k-i) * C(b+d-i, k-i) * (k-i)!
"""
ans = 0
for i in range(k + 1):
term = C[c][i] * C[d][i] % MOD * fact[i] % MOD * C[a][k - i] % MOD
n2 = b + d - i
m2 = k - i
if n2 >= 0:
term = (term * C[n2][m2]) % MOD
else:
term = 0
term = (term * fact[k - i]) % MOD
ans = (ans + term) % MOD
return ans
if __name__ == "__main__":
precompute()
a, b, c, d, k = list(map(int, input().split()))
ans = solve_expr1(a, b, c, d, k)
print(ans)
法2：动态规划
前面介绍的视角3的dp适用于任何形状的棋盘，那自然也适用于这题。设dp[i,j]表示棋盘前i行上放j个车的方案数，则：
$$
dp[i,j]=dp[i-1,j]+K \cdot dp[i-1,j-1]
$$
其中K是一个跟行号有关的函数 $K(i)$ ：K(i)=(a - j + 1) if i <= b else (a + c - j + 1)
另外，为了减少代码的运行时间，记得约束j（枚举放置的车的数目）的范围：j_lim = min(k, a) if i <= b else min(k, a + c)
MOD = 100003
MAX_N = 2005
a, b, c, d, k = list(map(int, input().split()))
dp = [[0] * MAX_N for _ in range(MAX_N)]
dp[0][0] = 1
for i in range(1, b + d + 1):
j_lim = min(k, a) if i <= b else min(k, a + c)
for j in range(j_lim + 1):
coeff = (a - j + 1) if i <= b else (a + c - j + 1)
dp[i][j] = (dp[i - 1][j] + (dp[i - 1][j - 1] if j > 0 else 0) * coeff % MOD) % MOD
print(dp[b + d][k])
[复制链接]
发表于 2026-4-15 23:44
|
发表于 2026-4-16 08:40
