打卡信奥刷题系列写到第 2901 篇今天聊的是洛谷 P5259出自 JSOI2013 的《游戏中的学问》。这题名字起得很有迷惑性乍一看像要设计什么游戏策略实际读完会发现它是一道特别纯正的组合计数动态规划题n 个人分成若干个小组每组至少 3 人组内围成一圈求方案总数对 p 取模。考点非常集中圆排列计数、递推建模、取模运算属于信奥提高组到省选之间反复出现的经典题型。如果你正在刷组合 DP或者想搞明白“分组圆排列”这类问题到底怎么下手这篇应该能帮上忙。下面我从数学建模讲到 C 实现再把提交时最容易翻车的几个点逐一说明。1. 先搞清楚“游戏中的学问”到底在数什么1.1 原题说的是什么事把题面翻译成人话就是有 n 个人编号各不相同要分成 k 个小组做游戏。每个小组的人数至少是 3 个太少没法玩。组内所有人围成一圈问一共有多少种分组方式。答案是一个很大的数题目要求对 p 取模输出。我第一次看到这个题的时候第一反应是什么博弈论、什么最优策略读了两遍才发现根本就是个计数题。题目里“游戏”两个字误导性极强实际上“学问”在组合数学这边。n 和 k 都在 1000 这个量级直接枚举分组方案是绝对不可能的暴力枚举的复杂度是天文数字。所以必须找到递推结构用动态规划去算。1.2 建模有标号的人、无标号的组、组内是圆排列动手写递推之前先要把模型拆干净。这个题有三个关键属性很多新手就是栽在这里第一人是不同的每个人有编号属于“有标号元素”。第二组和组之间不区分顺序也就是说“先分 A 组再分 B 组”和“先分 B 组再分 A 组”是同一种方案。第三组的内部不是一个普通的集合而是一个环。三个人坐成一圈和四个人坐成一圈本质上都是圆排列。圆排列有个重要结论s 个不同的人围成一圈方案数是 (s-1)!不是 s!。因为一个圈可以旋转转一下还是同一种坐法。这三个属性决定了这道题不能套普通的“分组组合数”公式。人不同意味着要乘排列组间无序意味着要考虑去重组内是环又意味着每种人数对应 (s-1)! 种内部结构。三者叠在一起公式会变得很复杂而且很难处理取模问题。1.3 为什么第一反应不是排列组合公式你可能会想直接用组合数学推一个闭式公式不是更优雅吗理论上可以写成一个多重求和先枚举每组的人数再乘上组合数、环排列数最后除以 k! 去掉组间顺序。但问题是这个公式写出来之后几乎没法用。且不说多重循环的复杂度问题光是组合数里的除法就够喝一壶的。题目只告诉你对 p 取模但没说 p 是质数。如果 p 是个合数组合数 C(n, m) 在模 p 意义下根本不能简单地用阶乘乘逆元算因为逆元可能不存在。这也是这题最阴险的地方后面我会专门展开讲。所以正确的打开方式是把整个计数过程变成一个只含加法和乘法的递推每一步都取模。这样无论 p 是什么正整数程序都能稳定跑出正确答案。2. 递推式是怎么想出来的从“那个人”切入的两类转移2.1 抓住最后加入的人组合计数 DP 里最常用的一个切入角度就是盯住一个特殊元素看他所在的“结构”长什么样。在这道题里我们盯住编号最大的人或者说“最后一个加入的人”记作 i。设 f[i][j] 表示 i 个人分成 j 个合法圆圈的方案数。现在考虑第 i 个人他必须属于某个圈。这个圈的人数只有两种可能第一种圈里至少有 4 个人第二种圈里恰好 3 个人。不可能更少因为每组至少 3 人。这两种情况正好对应两个互不重叠的转移方向。第一种情况圈里至少 4 个人。想象一下把第 i 个人从这个圈里抽走剩下的人还是 i-1 个圈还是 j 个而且每个圈仍然至少 3 个人完全合法。反过来任意一个 i-1 个人分成 j 个圈的合法方案把第 i 个人插进某一个圈里有多少种插法一个圈里有 s 个人就有 s 个空位但这 s 个空位分布在 j 个圈里总空位数就是 i-1。换句话说不管插到哪个圈、哪个位置方案数都是 i-1。所以这一项的贡献是 (i-1) 乘以 f[i-1][j]。第二种情况圈里恰好 3 个人。那么这个圈就是由第 i 个人和另外两个人组成的。先从之前的 i-1 个人里选出 2 个人选法是 C(i-1, 2)。三个人围成一圈圆排列数是 (3-1)! 2 种。剩下 i-3 个人要分成 j-1 个圈方案数是 f[i-3][j-1]。所以这一项的贡献是 C(i-1, 2) 乘以 2 再乘以 f[i-3][j-1]。C(i-1, 2) 乘以 2 正好等于 (i-1)(i-2)因为组合数的分母 2 被圆排列的 2 约掉了。合起来就是f[i][j] (i-1) * f[i-1][j] (i-1) * (i-2) * f[i-3][j-1]这个式子相当简洁而且全程只有乘法和加法取模非常安全。2.2 为什么组与组之间不需要排序这个递推式写出来之后很多同学会陷入一个疑问组不是无标号的吗为什么递推过程中没有除以 k!也没有乘以 j组间顺序是怎么自动消掉的答案是因为我们的构造过程天然给每个新圈安排了一个“锚点”。我们始终是从编号小的往编号大的方向处理人每当我们新开一个圈这个圈一定包含当前编号最大的那个人。换句话说每个圈在诞生的那一刻都绑定了一个“当前最大编号”的人这个人成为这个圈的天然标识。这样想就清楚了既然每个圈都能通过“包含的编号最大的人”来唯一识别那圈与圈之间就不存在排列顺序问题。你可以把 j 个圈看成 j 个有名字的容器名字就是各自圈里最大编号的人构造过程自动规避了重复。如果换一种思路先把 j 个组看成有编号的最后再除以 k!当然也能得到同一个答案但那个做法在取模意义下处理除法很麻烦远不如这个递推来得干净。为了让你彻底放心我们拿小数据手算验证一下。先看 f[3][1]。3 个人围成一圈圆排列数是 (3-1)! 2。用递推公式f[3][1] 2 * f[2][1] 2 * 1 * f[0][0] 0 2 2正确。再看 f[4][1]。4 个人围成一圈应该是 3! 6 种。递推f[4][1] 3 * f[3][1] 3 * 2 6正确。再看一个稍微复杂的f[6][2]。递推f[6][2] 5 * f[5][2] 5 * 4 * f[3][1]。f[5][2] 是 0因为 5 个人没法分成两个至少 3 人的圈。f[3][1] 是 2。所以结果是 0 20 * 2 40。手工验证一下 40 对不对6 个人分成两个 3 人圈。先选 3 个人进第一个圈C(6,3)20 种剩下 3 个人自动进第二个圈。但组间无序所以要除以 2得到 10。每个 3 人圈内部有 (3-1)!2 种圆排列两个圈就是 224。10440完全一致。这说明递推式和“组间无序”这个条件配合得非常好。2.3 初始化与边界条件递推式确定之后边界条件也要想清楚。f[0][0] 1表示 0 个人分成 0 个圈算一种空方案这是整个递推的地基。当 i 大于 0 时f[i][0] 应该是 0因为不可能有人却没圈。另外当 3*j i 时f[i][j] 也一定是 0因为每个圈至少 3 个人人数不够分。在代码实现里这些边界条件不用全部显式判断只需要保证数组下标不越界并且递推起点正确。核心循环里加一个 if (i 3) 来保护第二项就能避免负下标。3. C 代码落地滚动数组的实现与解释3.1 朴素二维 DP 的核心循环如果你不太熟悉滚动数组可以先写一个朴素版本理清思路。开一个二维数组 dp[i][j]按 i 从 1 到 n 循环。核心就三行for (int i 1; i n; i) { for (int j 1; j min(k, i / 3); j) { dp[i][j] dp[i - 1][j] * (i - 1) % p; if (i 3) { dp[i][j] (dp[i][j] dp[i - 3][j - 1] * (i - 1) % p * (i - 2)) % p; } } }这里的 j 上界取 min(k, i/3) 是个小优化。因为 i 个人最多只能分成 i/3 个圈超过这个数方案数必然是 0没必要算。朴素二维数组的空间是 (n1)*(k1)n 和 k 都是 1000 时大概 8MB其实也能过。但递推只依赖 i-1 和 i-3 两行完全没有必要保留所有历史状态。滚动数组不仅省内存也是一个值得养成的习惯因为以后会遇到很多 n 更大、开不下二维数组的变种题。3.2 滚动数组为什么要保留最近三层观察递推式 f[i][j] (i-1)f[i-1][j] (i-1)(i-2)*f[i-3][j-1]当前行会用到前 1 行和前 3 行的数据。所以至少需要保留最近 3 行的信息。常见的做法是开 4 行用 i % 4 作为当前行下标(i-1) % 4 作为上一行(i-3) % 4 作为上三行。这里有个容易搞混的点为什么不是 3 行而是 4 行因为当下标从 i-3 到 i 跨越了 3 个位置要保证这 3 个位置的行号都不冲突循环数组长度至少是 314。用 i % 4 可以做到 i、i-1、i-2、i-3 这四行互不相同。如果你偷懒只开 3 行那 i 和 i-3 会落到同一行数据会被覆盖结果直接错乱。完整可提交的 C 代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; long long p; cin n k p; if (3LL * k n) { cout 0 % p \n; return 0; } vectorvectorlong long dp(4, vectorlong long(k 5, 0)); dp[0][0] 1 % p; for (int i 1; i n; i) { int cur i % 4; fill(dp[cur].begin(), dp[cur].end(), 0); int maxj min(k, i / 3); for (int j 1; j maxj; j) { long long val 0; // 第 i 个人插入已有的某个圈 val (val dp[(i - 1 4) % 4][j] * (i - 1)) % p; // 第 i 个人与之前的两个人组成新圈 if (i 3) { val (val dp[(i - 3 4) % 4][j - 1] * (i - 1) % p * (i - 2)) % p; } dp[cur][j] val; } } cout dp[n % 4][k] % p \n; return 0; }这段代码有几处细节值得说一下。第一dp[0][0] 初始化为 1 % p是为了兼容 p 1 这种极端情况。如果 p 是 1任何数对 1 取模都是 0初始化为 0 也是对的但写成 1 % p 语义更完整。第二每轮循环开头必须 fill 当前行。因为滚动数组的同一行在 i 增加 4 之后会被再次使用如果不把旧数据清掉上一轮残留的 dp[cur][j] 会污染本轮结果。这是滚动数组最常见的坑我后面还会重点说。第三第二项里 dp[...][j-1] 的下标 j-1 不会越界因为内层循环从 j 1 开始j-1 最小是 0。而 dp[x][0] 在 i 大于 0 时始终是 0正好符合边界条件。3.3 当 3k 大于 n 时的快速判断代码一开头有一个提前退出if (3LL * k n)直接输出 0 % p。这个判断非常重要。一方面它是个正确的数学结论每个圈至少 3 个人k 个圈至少需要 3k 个人如果总人数不够方案数就是 0。另一方面它可以避免后面的循环做大量无用功甚至避免某些粗心写法下的数组访问异常。我们后面在边界处理那一节还会回头提这个。4. 提交前必查的四个坑每一个都有人挂过4.1 模数 p 不保证是质数千万别用逆元这是这道题最阴的一个坑没有之一。很多同学拿到计数题第一反应是套组合数公式然后用费马小定理求逆元。但费马小定理成立的前提是模数 p 是质数而这道题从头到尾都没保证 p 是质数。如果 p 是个合数比如 8 或者 12那很多数字在模 p 意义下根本没有逆元算出来的组合数全是错的。这题的正确姿势就是老老实实用递推因为递推式里只有加法和乘法对任意正整数 p 取模都是安全的。我当年第一次写的时候习惯性地跑去预处理阶乘和逆元结果样例都过不了调了半天才发现问题出在“想当然”三个字上。所以请记住一个通用原则题目只写“对 p 取模”而没说“p 是质数”时你的算法里绝对不能出现除法。组合数、排列数要么用递推展开要么用其他不依赖逆元的方式计算。4.2 乘法溢出问题再看一眼递推式中的 (i-1) * (i-2)。i 最大 1000 左右时这个乘积大约是 10^6看起来不大。但要再乘以 dp 值而 dp 值在取模前可能接近 pp 如果取到 10^9 级别三者相乘就是 10^15这已经超出 int 的范围了。所以代码里所有涉及乘法累加的变量以及读入的 p都必须用 long long。如果你用 int 去读 pp 一大直接溢出成负数后面所有取模运算全都乱套。这种错误非常隐蔽因为小数据可能碰巧能过大数据就 WA。建议做这类计数题时直接默认所有数值都用 long long不要在一开始就想着省那一点内存。顺带提一句代码里我写了 dp[(i-34)%4][j-1] * (i-1) % p * (i-2)这里每乘一步都取模一次可以防止乘法中间结果继续膨胀。虽然这个量级下 long long 已经够用但这个习惯在更大的数据范围下能救命。4.3 滚动数组忘了清空当前层滚动数组空间优化的代价就是你得自己管理“过期数据”。我见过不少选手递推公式写对了循环也对就是忘了在每轮开头 fill 当前行结果同一个 dp[cur][j] 里残留着 i-4 轮的数据被当成当前轮的结果继续参与计算答案自然莫名其妙。这个问题为什么难查因为小数据量下残留值可能恰好是 0程序能跑对数据一多残留的非零值就开始干扰结果报错毫无规律。检查技巧就一条把滚动数组版本和朴素二维版本在小范围 n、k 下逐项对比任何一个数字对不上先检查 fill 有没有写。另外我建议把滚动数组的每轮 fill 写在循环体的第一行并养成条件反射。不要觉得自己这次不会忘刷题量上去之后滚动数组会用在各种地方这个习惯越早养成越好。4.4 边界初始化负下标与空方案最后一个高频坑是边界处理。递推里第二项需要访问 dp[i-3][j-1]当 i 小于 3 的时候i-3 是负数直接访问会越界或者访问到垃圾值。所以代码里用 if (i 3) 来保护这一项。另一个边界是 f[0][0] 1。很多新手会写成 f[0][0] 0导致整个递推的起点崩塌算出来的方案数全部为 0。记住0 个人分成 0 个圈是 1 种方案这是一个“空方案”的约定类似于乘法单位元。有了这个 1f[3][1] 才能从第二项得到 2整个递推才转得起来。如果题目输入的 k 很大比如 1000 个人、k500每组至少 3 人明显不可能那直接用 if (3LL * k n) 输出 0既省时间又防止 j 上限算错导致的越界。千万不要在这种地方抱着侥幸心理。5. 这一类“分组圆排列”计数题的通用解法与变式5.1 先看第一类斯特林数刷完这道题我建议你把它和第一类斯特林数放在一起对比记忆。第一类斯特林数 s[i][j] 表示把 i 个有标号元素分成 j 个圆排列的方案数它的递推是s[i][j] s[i-1][j-1] (i-1) * s[i-1][j]第一项表示第 i 个人自己单独成一个圈第二项表示把第 i 个人插入已有某个圈。而本题规定每个圈至少 3 人所以第一项“单独成圈”被禁止变成了“拉上两个人组成新圈”。两个递推思路完全同构问题每个圈的最小人数新开圈的方案递推式第一类斯特林数1第 i 人单独成圈1 种s[i][j] s[i-1][j-1] (i-1) * s[i-1][j]本题 P52593第 i 人再拉 2 人成圈C(i-1,2)*2 种f[i][j] (i-1) * f[i-1][j] (i-1)(i-2) * f[i-3][j-1]这种对比不是简单的记公式而是让你看清组合计数 DP 里“分类讨论最后一个元素”的核心思想。刷题时遇到新题别急着搜题解先问问自己能不能盯住一个特殊元素按他所在结构的大小分类5.2 更一般的套路枚举“最大元素所在结构”把上面的思想再抽象一层就是这类分组计数题的通用解法。设每个组最少要 m 个人。考虑编号最大的人 i他要么加入某个已有组这种转移数是 i-1要么作为新组的“核心”从剩下的人里挑 m-1 个和他组成新组。选人加排列的细节可以用一个排列数 P(i-1, m-1) 来表达也就是从 i-1 个人里有序地挑出 m-1 个人并按圆排列方式排好。于是通用递推可以写成f[i][j] (i-1) * f[i-1][j] P(i-1, m-1) * f[i-m][j-1]当 m1 时P(i-1,0)1这个式子退化成第一类斯特林数。当 m2 时P(i-1,1)i-1但两个人在圆桌上的排列只有 1 种所以其实是 f[i][j] (i-1)*f[i-1][j] (i-1)*f[i-2][j-1]。当 m3 时就是我前面推导的本题形式。掌握这个通式之后以后遇到“每组至少多少人”的变体你可以在 1 分钟内写出正确的递推。5.3 几个能直接套用和变形的方向如果你想把这道题吃透我建议接下来做这几个方向的思考。第一如果每组至少 4 人递推会变成什么样套用通用公式把 m 改成 4 即可。写的时候注意排列数 P(i-1, 3) (i-1)(i-2)(i-3)不要漏乘。第二如果每组内部不是围成圆圈而是排成一条队伍也就是“链”而不是“环”那内部排列数从 (s-1)! 变成 s!。这时候递推里的系数要相应调整本质思路不变。第三如果题目把“组分好”明确分组有编号要求区分第 1 组、第 2 组那么无标号答案乘以 k! 即可。注意只有每组都至少有人时才不会出现重复本题每组至少 3 人天然满足这个条件。第四如果模数是质数且 n 特别大可以考虑用生成函数或多项式技巧。第一类斯特林数的生成函数是 x(x1)(x2)... 这类乘积形式本题则涉及截断项但那就是另一层难度了。现阶段把递推吃透足够应付绝大多数信奥题目。最后再分享一个刷题习惯。我在做这题时会把“p 不保证质数禁止逆元”和“组合 DP 要抓住编号最大的元素”两条笔记写在同一个文档里。后面遇到 P5259 类似题或者任何“分组环排列”计数题先检查模数性质再设计递推基本不会再犯低级错误。这道题本身不难但它代表的那类思维值得反复咀嚼。