企业官网建设流程全解析

2025年蓝桥杯省 B 结束那天晚上，我一直在复盘这道 P12131《客流量上限》。题目难度标的是普及+，考点写在标题里：数论、逆元。说实话，这类“公式一眼能看懂，代码一写就各种爆”的题，比纯算法模板题更适合拿出来做一次完整复盘。当时我看到“客流量上限”这四个字，第一反应是贪心或者二分，结果读完题才发现，它要的是一套组合计数，而且所有取模除法都绕不开乘法逆元。这篇文章就围绕这道题，把逆元从原理到代码、从推导到调试全部串一遍，给正在备战蓝桥杯或者想补数论短板的同学一份可以直接照着做的完整笔记。

1. 题目概况：省 B “客流量上限”到底考什么

1.1 我记忆里的题面

先按考场回忆和民间题解还原一下题目大意。景区里有 n 个游玩项目，每个项目每天最多接待 k 名游客，也就是“客流量上限”都是同一个值 k。某一天景区一共来了 S 名游客，每个游客只能选择一个项目游玩，而且每个项目当天接待的人数不能超过上限 k。现在要求计算：把 S 名游客全部分配到 n 个项目里，一共有多少种合法分配方案？答案对 1e9+7 取模。

数据范围我印象里大概是：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 人。容斥的做法是先“构造非法”，强制某些项目至少分到 k+1 人，然后把它们的方案数从总数里减掉，重复部分再加回来。由于所有项目上限相同，容斥项能压缩成只依赖“选几个项目来超限”的形式。

第三条线是逆元。组合数 C(a, b) 在取模 1e9+7 的情况下，分母的阶乘不能直接除，必须把除法变成乘上分母的逆元。这里用费马小定理，因为 1e9+7 是质数，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 费马小定理与快速幂求单个逆元

求逆元最常见的方法就是费马小定理。因为 1e9+7 是质数，对于任意不是它倍数的整数 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 数组，我们就能再算 invfact：

vector<long 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 的数据毫无压力。

我在线下测过，用快速幂逐个求逆和线性递推求逆，在 n=1e6 时时间差接近十倍。省赛每一毫秒都很宝贵，规矩做法就是线性递推。

2.4 三种求逆方式对比

如果模数不是质数，比如 1e9+8，费马小定理就不能直接用，得用扩展欧几里得。但竞赛题里出题人通常都用 1e9+7 或 998244353 这类质数模数，所以费马小定理是首选。遇到“非质数模数”的题，先用扩展欧几里得保证正确性，别一上来就套快速幂。

3. 把题意翻译成公式：从隔板法到容斥

3.1 隔板法：无上限情况下的答案

先处理一个无上限的版本：把 S 个游客分给 n 个项目，每个项目至少 0 人，没有其他限制。这个问题等价于在 S 个相同小球之间放 n-1 块隔板，把它们分成 n 段，有些段可以空。方案数是 C(S + n - 1, n - 1)。这是隔板法的标准结论，写在草稿纸上验证一下：n=3, S=2，公式给出 C(4,2)=6，确实是六种分配。

我建议把这一步的“为什么”记牢：把 S 个球和 n-1 块隔板放在一起排列，隔板的位置决定分段结果。因为每段可以为空，所以不是直接从 S 个缝隙里选，而是从 S+n-1 个位置里选 n-1 个放隔板。这个细节很多人会弄反。

3.2 加入上限：用容斥砍掉非法方案

现在每个项目最多 k 人。非法情况就是有至少一个项目的人数超过 k，也就是至少一个项目 >= k+1 人。

容斥原理的经典写法是：

总方案数 = 无限制方案数 - 至少 1 个项目超限的方案数 + 至少 2 个项目超限的方案数 - 至少 3 个项目超限的方案数 + ...

关键在于如何计算“指定 j 个项目超限”的方案数。比如先指定某 j 个项目，让它们每个人先拿 k+1 个游客，剩下的人再自由分配。这样剩余人数是 S - j*(k+1)，剩余的项目仍然是 n 个，而且不设上限。此时方案数就是：

C(S - j*(k+1) + n - 1, n - 1)

而“指定哪 j 个项目超限”有 C(n, j) 种选择。因为所有项目的上限相同，所以只需要知道 j，不需要知道具体是谁，容斥的每一项就能直接写出来。

于是整道题的最终答案公式是：

Ans = Σ_{j=0}^{min(n, floor(S/(k+1)))} (-1)^j * C(n, j) * C(S - j*(k+1) + n - 1, n - 1)

3.3 边界与枚举上限为什么是 floor(S/(k+1))

公式里的枚举上限不是 n，而是 floor(S/(k+1))。这个点特别容易踩坑。

原因很简单：如果你强制 j 个项目每人拿 k+1 人，那已经花掉了 j*(k+1) 个游客。如果这个数超过了 S，剩余人数就是负数，后面那个组合数没有意义。所以合法的 j 必须满足 j*(k+1) <= S，也就是 j <= floor(S/(k+1))。

同时 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/(k+1))) 次，每次做两次组合数查询，组合数每次 O(1)。总复杂度大致是 O(n + S)，在 n、S 不超过 1e6 时完全轻松。如果 n 和 S 到了 1e7，数组内存会到 80MB 左右，需要谨慎，但省赛一般不会那么夸张。

内存方面：三个长度为 maxNeed 的 long long 数组，1e6 时约 24MB，完全没问题。如果题目换成 int 数组，还能再省一半。

4.4 用样例反推验证公式

我习惯在正式提交前，用最小组数据手算一遍。比如 n=2, k=1, S=2。两个项目，每个最多 1 人，总共 2 人，只能一个项目 1 人一个项目 1 人，答案应该是 1。套公式：

j=0：C(2,0) * C(2-0+2-1, 2-1) = C(3,1) = 3 j=1：- C(2,1) * C(2-2+2-1, 2-1) = -2 * C(1,1) = -2 j=2：floor(2/2)=1，所以 j=2 不在枚举范围。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/(k+1)) 取 min，当 S 很小而 n 很大时，S - j*(k+1) 会变成负数。此时 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 i=2; i<=n; i++) 不会执行，不会有问题。

5.5 输入数据的坑

这道题输入里 n、S、k 都没有特殊陷阱，都是正整数。但比赛中我见过有人用 int 存 S，S 到 1e9 级别时直接溢出。建议所有可能超过 2e9 的变量都用 long long，尤其是这种组合数题，中间临时变量很多，编译器不会帮你检查溢出。

5.6 考场时间分配：别在第一题上恋战

蓝桥杯省赛的整体节奏非常重要。我当时大概先用 15 分钟读完了所有题，发现这道“客流量上限”是典型的“会者不难”类型，就决定先写它。但如果你的逆元基础不牢，我建议先跳过，最后留 40 分钟专门做。千万别在写代码过程中临时去翻逆元公式，那样既浪费时间又容易把心态搞崩。

6. 逆元题的通法：从省 B 到省选的延伸

6.1 看到哪些特征就该想到逆元

这类题通常有很强的信号，我总结成三条：

一是题目里出现“答案对 1e9+7 取模”或“答案对 998244353 取模”，且公式中有除法。二是题目让你算组合数、排列数、多重集排列数，或者让你算概率期望并取模。三是区间查询里需要“前缀积的区间删除”，这种必须用逆元还原左端点的贡献。

反过来，如果题目只有加法、乘法和取模，没有除法，那就不需要逆元，不要为了用逆元而强行用，否则只会引入新的 bug。

6.2 没有逆元时的替代方案

模数不是质数时，费马小定理不能用。遇到这种情况，可以用扩展欧几里得求逆元，前提是被求逆的数与模数互质。如果两者不互质，逆元根本不存在，此时只能换一条路，比如用动态规划预处理组合数，或者用质因数分解分别计算结果再中国剩余定理合并。这种题目竞赛里不常见，但偶尔会作为防 AK 题出现，知道存在即可。

6.3 三道值得刷的同类模板题

• 区间乘积查询：维护前缀积和逆元，这道题和“客流量上限”的变形几乎一模一样。
• 组合数取模的大数据版：当 n 超过 MOD 时，需要用到卢卡斯定理，本质上是逆元的扩展应用。
• 概率 DP 取模：经典题“小明掷骰子到达终点的期望步数模 MOD”，它把分数化成逆元，再和 DP 结合，难度比省 B 稍高，但对理解逆元的本质帮助很大。

我通常建议备赛选手在刷题时按“模板题 -> 公式推导题 -> 综合题”的顺序推进。P12131 正好处在第二层，属于看一眼知道用什么，但推导过程依然需要自己走一遍的题。这类题的价值不在于考场上能否一次 AC，而在于你每做一遍，对模运算和数论基础的理解都会加深一些。

7. 赛后的一点个人体会

这次省 B 复盘下来，我最深的感觉是：竞赛里很多“常识性操作”靠的是平时大量的刻意练习。逆元这个概念，我在三年前第一次接触时也觉得抽象，什么费马小定理、线性递推，背完就忘。后来连续刷了十几道组合数学题，才真正形成条件反射：看到公式里有除法、看到取模质数，大脑自动就开始准备阶乘和逆元表。

如果你现在也被逆元搞得头疼，不用急，就按照这篇文章的顺序，先把单个逆元怎么求搞明白，再写一遍线性递推预处理的模板，最后拿这道“客流量上限”的完整公式跑通一遍。这个过程不需要任何天赋，只需要一个下午的专注。下次再遇到类似题，你连公式都不用现推，手会比脑子更快。