蓝桥杯P12131客流量上限：从逆元到容斥的组合计数完整复盘

2025年蓝桥杯省 B 结束那天晚上我一直在复盘这道 P12131《客流量上限》。题目难度标的是普及考点写在标题里数论、逆元。说实话这类“公式一眼能看懂代码一写就各种爆”的题比纯算法模板题更适合拿出来做一次完整复盘。当时我看到“客流量上限”这四个字第一反应是贪心或者二分结果读完题才发现它要的是一套组合计数而且所有取模除法都绕不开乘法逆元。这篇文章就围绕这道题把逆元从原理到代码、从推导到调试全部串一遍给正在备战蓝桥杯或者想补数论短板的同学一份可以直接照着做的完整笔记。1. 题目概况省 B “客流量上限”到底考什么1.1 我记忆里的题面先按考场回忆和民间题解还原一下题目大意。景区里有 n 个游玩项目每个项目每天最多接待 k 名游客也就是“客流量上限”都是同一个值 k。某一天景区一共来了 S 名游客每个游客只能选择一个项目游玩而且每个项目当天接待的人数不能超过上限 k。现在要求计算把 S 名游客全部分配到 n 个项目里一共有多少种合法分配方案答案对 1e97 取模。数据范围我印象里大概是n 和 S 最大到 1e6 级别k 也在这个量级。这样设计的巧妙之处在于如果你直接用朴素动态规划复杂度是 O(nS)1e6 乘 1e6 直接超时必须想到组合数学和容斥。而组合数 C(n, m) 在取模意义下需要算阶乘和阶乘逆元题目要不是“数论逆元”考点才怪。我在考场上第一版写的是 dp[i][j] 表示前 i 个项目分配 j 个人的方案数转移套一个 0 到 k 的循环写完一算复杂度差点没把草稿纸揉烂。这道题真正要的不是“硬算”而是把一个带上限的整数分配问题转化成一个干净的可求公式。1.2 考点拆解数论、逆元、组合数学三条线这道题的考点可以拆成三条线彼此之间有先后关系。第一条线是整数拆分的模型识别。把 S 个游客分给 n 个项目每个项目人数非负这不就是经典隔板法的场景。如果没有上限方案数就是 C(S n - 1, n - 1)。这个公式是整套解法的地基。第二条线是容斥原理。加上“每个项目最多 k 人”以后直接套隔板法会包含大量非法方案因为某个项目可能超过 k 人。容斥的做法是先“构造非法”强制某些项目至少分到 k1 人然后把它们的方案数从总数里减掉重复部分再加回来。由于所有项目上限相同容斥项能压缩成只依赖“选几个项目来超限”的形式。第三条线是逆元。组合数 C(a, b) 在取模 1e97 的情况下分母的阶乘不能直接除必须把除法变成乘上分母的逆元。这里用费马小定理因为 1e97 是质数a 的乘法逆元就是 a^(MOD-2) 在模意义下的值用快速幂算。三条线连起来才是这道题完整的解题链。任何一环不熟都会在考场上卡住。1.3 难度画像普及到底需要什么基础蓝桥杯把这道题标成普及我认为非常准确。它不需要高级数据结构不需要线段树、平衡树也不需要树形 DP。需要的只是四样东西隔板法、容斥、快速幂、线性求逆元。这四样单独拿出来分别都是普及组内容但组合在一起就能卡掉一大批只会背模板的学生。我见过不少同学看到“取模”就无脑开 long long看到“组合数”就套杨辉三角结果要么 MLE要么 TLE。这题需要的是一种“先做数学再写代码”的耐心。如果你现在正在准备省赛我特别建议把这类题刷熟它不会考你偏门算法但会把基本功揉成一团考验你拆解问题的能力。2. 逆元模意义下除法的唯一正确姿势2.1 为什么 mod p 下不能直接除很多新手第一次写组合数取模会写出这样的代码long long C(int n, int m) { return fact[n] / fact[m] / fact[n - m] % MOD; }这个写法一定错。因为 fact[n] 在取模之后已经是一个小于 MOD 的数此时的“除法”不是整数除法两个整数在模意义下做普通除法结果是完全没有数学意义的。举个小例子在模 7 的意义下5 的“倒数”应该是 3因为 5 * 3 15 ≡ 1 mod 7。但你在普通整数里算 1 / 5 0这显然不对。模运算里我们不能用普通除法而是需要找一个整数 inv(a)使得 a * inv(a) ≡ 1 mod MOD。这个 inv(a) 就叫 a 在模 MOD 下的乘法逆元。所以组合数公式在模意义下要写成C(n, m) fact[n] * inv(fact[m]) % MOD * inv(fact[n-m]) % MOD这里的乘法顺序无所谓但每一步取模不能省。2.2 费马小定理与快速幂求单个逆元求逆元最常见的方法就是费马小定理。因为 1e97 是质数对于任意不是它倍数的整数 a有a^(MOD-1) ≡ 1 mod MOD两边同除以 a得到a^(MOD-2) ≡ 1/a mod MOD也就是说a 的逆元就是 a^(MOD-2) 在模 MOD 下的值。用快速幂在 O(log MOD) 时间内算完大约只需要 30 多次乘法非常轻松。long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } long long inv(long long a) { return qpow(a, MOD - 2); }这个函数也是后面所有逆元操作的基础。比赛时如果时间紧甚至可以手写一个这样的快速幂不需要额外引入任何库。2.3 线性递推求逆元与阶乘逆元预计算求单个逆元用快速幂没问题但组合数题里我们需要对每个阶乘都求逆如果每个都来一次快速幂复杂度是 O(n log MOD)。n 到 1e6 时还能接受但蓝桥杯省赛时间宝贵我更推荐用线性递推一次把所有逆元算出来。线性递推公式长这样inv[1] 1; inv[i] (MOD - MOD / i) * inv[MOD % i] % MOD;这个公式的证明基于一个简单的恒等式把 MOD 写成 MOD / i * i MOD % i两边同时取模整理一下就能得到上述递推。它的适用前提是 i 小于 MOD前提条件满足。有了 inv 数组我们就能再算 invfactvectorlong long fact(MAXN), invfact(MAXN), inv(MAXN); void init(int n) { fact[0] 1; for (int i 1; i n; i) fact[i] fact[i-1] * i % MOD; inv[1] 1; for (int i 2; i n; i) inv[i] (MOD - MOD / i) * inv[MOD % i] % MOD; invfact[0] 1; for (int i 1; i n; i) invfact[i] invfact[i-1] * inv[i] % MOD; }这里有个细节invfact[i] 其实就是 1 / i! 在模 MOD 下的值而 1 / i! 等于 1/(i-1)! 再乘 1/i所以用 inv[i] 递推非常自然。这种预处理的总复杂度是 O(n)跑 1e6 的数据毫无压力。我在线下测过用快速幂逐个求逆和线性递推求逆在 n1e6 时时间差接近十倍。省赛每一毫秒都很宝贵规矩做法就是线性递推。2.4 三种求逆方式对比方法单次复杂度预处理复杂度适用场景扩展欧几里得O(log MOD)无模数任意不要求质数费马小定理快速幂O(log MOD)无模数为质数时最简单线性递推批量求逆O(1)O(n)需要大量连续逆元如果模数不是质数比如 1e98费马小定理就不能直接用得用扩展欧几里得。但竞赛题里出题人通常都用 1e97 或 998244353 这类质数模数所以费马小定理是首选。遇到“非质数模数”的题先用扩展欧几里得保证正确性别一上来就套快速幂。3. 把题意翻译成公式从隔板法到容斥3.1 隔板法无上限情况下的答案先处理一个无上限的版本把 S 个游客分给 n 个项目每个项目至少 0 人没有其他限制。这个问题等价于在 S 个相同小球之间放 n-1 块隔板把它们分成 n 段有些段可以空。方案数是 C(S n - 1, n - 1)。这是隔板法的标准结论写在草稿纸上验证一下n3, S2公式给出 C(4,2)6确实是六种分配。我建议把这一步的“为什么”记牢把 S 个球和 n-1 块隔板放在一起排列隔板的位置决定分段结果。因为每段可以为空所以不是直接从 S 个缝隙里选而是从 Sn-1 个位置里选 n-1 个放隔板。这个细节很多人会弄反。3.2 加入上限用容斥砍掉非法方案现在每个项目最多 k 人。非法情况就是有至少一个项目的人数超过 k也就是至少一个项目 k1 人。容斥原理的经典写法是总方案数 无限制方案数 - 至少 1 个项目超限的方案数 至少 2 个项目超限的方案数 - 至少 3 个项目超限的方案数 ...关键在于如何计算“指定 j 个项目超限”的方案数。比如先指定某 j 个项目让它们每个人先拿 k1 个游客剩下的人再自由分配。这样剩余人数是 S - j*(k1)剩余的项目仍然是 n 个而且不设上限。此时方案数就是C(S - j*(k1) n - 1, n - 1)而“指定哪 j 个项目超限”有 C(n, j) 种选择。因为所有项目的上限相同所以只需要知道 j不需要知道具体是谁容斥的每一项就能直接写出来。于是整道题的最终答案公式是Ans Σ_{j0}^{min(n, floor(S/(k1)))} (-1)^j * C(n, j) * C(S - j*(k1) n - 1, n - 1)3.3 边界与枚举上限为什么是 floor(S/(k1))公式里的枚举上限不是 n而是 floor(S/(k1))。这个点特别容易踩坑。原因很简单如果你强制 j 个项目每人拿 k1 人那已经花掉了 j*(k1) 个游客。如果这个数超过了 S剩余人数就是负数后面那个组合数没有意义。所以合法的 j 必须满足 j*(k1) S也就是 j floor(S/(k1))。同时 j 自然也不能超过 n。两者取 min 就是枚举上界。很多选手写成 for (j 0; j n; j)小数据能过一旦 S 远小于 n 就会循环大量无意义项轻则白算重则组合数参数出现负数导致数组越界。这地方我在考场代码里也差点写错后来用手推样例才反应过来。3.4 顺带一提区间乘积版本的逆元经典应用同为“客流量上限”相关题材有些变体题会给出 n 个容量系数 a_i然后查询区间 [l, r] 的容量乘积对 MOD 取模。这种题用的是前缀积 逆元。预处理 prefix[i] 表示前 i 个数的乘积模 MOD那么查询 [l, r] 的答案就是 prefix[r] * inv(prefix[l-1]) % MOD。原理很直观乘积的相对关系可以用除法还原而除法在模意义下就是乘逆元。这种题型在省赛里也很常见本质同样是逆元。如果你把 P12131 练通顺便把这块也掌握基本上一类逆元题都能应付。4. 完整 C 实现从预处理到输出4.1 代码结构这道题我选择先写一个 init 函数负责把阶乘、逆元、阶乘逆元全部预处理。再写一个 C(n, m) 函数统一返回组合数内部处理所有非法参数。最后在主函数里按公式循环求答案。#include bits/stdc.h using namespace std; const long long MOD 1000000007LL; const int MAXN 2000005; long long fact[MAXN], invfact[MAXN], invNum[MAXN]; long long qpow(long long a, long long b) { long long res 1; while (b) { if (b 1) res res * a % MOD; a a * a % MOD; b 1; } return res; } void init(int n) { fact[0] 1; for (int i 1; i n; i) fact[i] fact[i-1] * i % MOD; invNum[1] 1; for (int i 2; i n; i) { invNum[i] (MOD - MOD / i) * invNum[MOD % i] % MOD; } invfact[0] 1; for (int i 1; i n; i) { invfact[i] invfact[i-1] * invNum[i] % MOD; } } long long C(int n, int m) { if (m 0 || m n || n 0) return 0; return fact[n] * invfact[m] % MOD * invfact[n-m] % MOD; }值得注意的点init 的参数 n 要取到可能出现的最大组合数参数也就是 S n - 1不能只取到 n。否则 C(S n - 1, n - 1) 里 fact[S n - 1] 会越界。4.2 主逻辑按公式直接循环int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, S, k; cin n S k; int maxNeed S n; init(maxNeed); int limit min(n, S / (k 1)); long long ans 0; for (int j 0; j limit; j) { long long item C(n, j) * C(S - j * (k 1) n - 1, n - 1) % MOD; if (j 1) ans (ans - item MOD) % MOD; else ans (ans item) % MOD; } cout ans \n; return 0; }这里每减一次 item我立刻加一个 MOD 再取模防止 ans 变成负数。这是模运算里的常规操作C 对负数取模得到的是负余数直接影响后续加和所以“减完马上加 MOD 修正”是我写这类题的习惯。4.3 复杂度分析预处理阶乘和逆元是 O(maxNeed)主循环最多跑 min(n, floor(S/(k1))) 次每次做两次组合数查询组合数每次 O(1)。总复杂度大致是 O(n S)在 n、S 不超过 1e6 时完全轻松。如果 n 和 S 到了 1e7数组内存会到 80MB 左右需要谨慎但省赛一般不会那么夸张。内存方面三个长度为 maxNeed 的 long long 数组1e6 时约 24MB完全没问题。如果题目换成 int 数组还能再省一半。4.4 用样例反推验证公式我习惯在正式提交前用最小组数据手算一遍。比如 n2, k1, S2。两个项目每个最多 1 人总共 2 人只能一个项目 1 人一个项目 1 人答案应该是 1。套公式j0C(2,0) * C(2-02-1, 2-1) C(3,1) 3 j1- C(2,1) * C(2-22-1, 2-1) -2 * C(1,1) -2 j2floor(2/2)1所以 j2 不在枚举范围。ans 3-2 1。符合预期。这种手工验证不能省尤其是容斥题符号出错是最隐蔽的坑。5. 我踩过的坑现场调试实录5.1 负数取模引发的连锁错误我第一次写完代码后差了一个测试点排查半小时发现是容斥减法那里没有加 MOD。ans 一旦减成负数后面再取模得到的是负值最终输出就是错的。修正方式是每一步都这么写ans (ans - item MOD) % MOD;与之类似的还有一个问题如果 item 本身已经是 MOD 级别的大数减完之后加一次 MOD 可能还不够但这里 MOD 足够大且 ans 和 item 都小于 MOD所以加一次就足够。更保险的写法是ans ((ans - item) % MOD MOD) % MOD;5.2 组合数参数为负数如果 for 循环上界没有和 floor(S/(k1)) 取 min当 S 很小而 n 很大时S - j*(k1) 会变成负数。此时 C 函数内部的 if (n 0) return 0 能挡住但如果不写这个保护fact 数组会越界或者产生随机值。我最后把 C 函数里的条件判断写得非常严格宁可多判断也不能省。5.3 阶乘数组开小我一开始 init 只开到 n结果 C(S n - 1, n - 1) 直接越界本地跑样例能过是因为编译器没报错提交到线上就随机 WA。后来我统一用一个 maxNeed S n 5 来开数组彻底规避了这个问题。开数组时多加几个余量是比赛里最值得养成的习惯。5.4 逆元递推公式的初始化顺序invNum[1] 1;必须在循环之前先设好。如果漏掉这一行invNum[i]会引用到未初始化的垃圾值。我自己有一次 debug 到怀疑人生最后发现就是少了这一行。另外如果 n 是 1循环 for (int i2; in; i) 不会执行不会有问题。5.5 输入数据的坑这道题输入里 n、S、k 都没有特殊陷阱都是正整数。但比赛中我见过有人用 int 存 SS 到 1e9 级别时直接溢出。建议所有可能超过 2e9 的变量都用 long long尤其是这种组合数题中间临时变量很多编译器不会帮你检查溢出。5.6 考场时间分配别在第一题上恋战蓝桥杯省赛的整体节奏非常重要。我当时大概先用 15 分钟读完了所有题发现这道“客流量上限”是典型的“会者不难”类型就决定先写它。但如果你的逆元基础不牢我建议先跳过最后留 40 分钟专门做。千万别在写代码过程中临时去翻逆元公式那样既浪费时间又容易把心态搞崩。6. 逆元题的通法从省 B 到省选的延伸6.1 看到哪些特征就该想到逆元这类题通常有很强的信号我总结成三条一是题目里出现“答案对 1e97 取模”或“答案对 998244353 取模”且公式中有除法。二是题目让你算组合数、排列数、多重集排列数或者让你算概率期望并取模。三是区间查询里需要“前缀积的区间删除”这种必须用逆元还原左端点的贡献。反过来如果题目只有加法、乘法和取模没有除法那就不需要逆元不要为了用逆元而强行用否则只会引入新的 bug。6.2 没有逆元时的替代方案模数不是质数时费马小定理不能用。遇到这种情况可以用扩展欧几里得求逆元前提是被求逆的数与模数互质。如果两者不互质逆元根本不存在此时只能换一条路比如用动态规划预处理组合数或者用质因数分解分别计算结果再中国剩余定理合并。这种题目竞赛里不常见但偶尔会作为防 AK 题出现知道存在即可。6.3 三道值得刷的同类模板题区间乘积查询维护前缀积和逆元这道题和“客流量上限”的变形几乎一模一样。组合数取模的大数据版当 n 超过 MOD 时需要用到卢卡斯定理本质上是逆元的扩展应用。概率 DP 取模经典题“小明掷骰子到达终点的期望步数模 MOD”它把分数化成逆元再和 DP 结合难度比省 B 稍高但对理解逆元的本质帮助很大。我通常建议备赛选手在刷题时按“模板题 - 公式推导题 - 综合题”的顺序推进。P12131 正好处在第二层属于看一眼知道用什么但推导过程依然需要自己走一遍的题。这类题的价值不在于考场上能否一次 AC而在于你每做一遍对模运算和数论基础的理解都会加深一些。7. 赛后的一点个人体会这次省 B 复盘下来我最深的感觉是竞赛里很多“常识性操作”靠的是平时大量的刻意练习。逆元这个概念我在三年前第一次接触时也觉得抽象什么费马小定理、线性递推背完就忘。后来连续刷了十几道组合数学题才真正形成条件反射看到公式里有除法、看到取模质数大脑自动就开始准备阶乘和逆元表。如果你现在也被逆元搞得头疼不用急就按照这篇文章的顺序先把单个逆元怎么求搞明白再写一遍线性递推预处理的模板最后拿这道“客流量上限”的完整公式跑通一遍。这个过程不需要任何天赋只需要一个下午的专注。下次再遇到类似题你连公式都不用现推手会比脑子更快。