企业官网建设流程全解析

我看过不少人刷题刷到“阶乘逆元”和“最大子数组和Kadane”时，会下意识把它们当两个孤立的知识点记：一个是数论里的取模运算，一个是动态规划里的经典套路。但从实际刷题和比赛的角度看，它们经常被放进同一道题、同一张题单，甚至同一个思维框架里。你如果只背板子，不搞明白背后的数学和状态设计，比赛时很容易在一堆细节上翻车。这篇文章就按我平时做题的经验，把这两个东西拆开揉碎，讲清楚它们是什么、为什么有效、怎么写不踩坑。

1. 为什么把这两个知识点放在一起聊

1.1 它们分别解决什么问题

先说结论：阶乘逆元主要解决“在模素数 p 下计算组合数 nCk 的效率问题”，而 Kadane 算法解决“在数组中找最大连续子数组和”的 O(n) 扫描问题。两个问题的底层套路完全不同，但它们在竞赛题里的出场方式经常是一前一后，比如某道题前半部分需要计数，后半部分需要在统计后的数组上跑最大子段和。

• 阶乘逆元：当 n 的规模到达 10^5、10^6，且计算 C(n,k) 要对 1e9+7 取模时，直接算阶乘和除法会溢出或产生浮点数误差，所以要用预处理的阶乘数组+逆元数组，把每次组合数查询压到 O(1)。
• Kadane：给你一个可能包含负数的数组，找出一个连续子数组，使其和最大。朴素做法至少要 O(n^2)，Kadane 用一次遍历 O(n) 解决，空间也可以压到 O(1)。

从解决的问题形态上看，一个是“组合计数”，一个是“连续段最值”。但这两类问题都必须处理好“边界条件”和“极端数据”，比如全负数数组、取模后出现负数、组合数参数不合法等。这些细节是很多人会错的第一道门槛。

1.2 什么场景下会“同框出现”

我举几个常见的组合场景：

• 在动态规划里，dp 转移方程涉及组合数 C(len, k)，而数组上又要求某个连续区间的最值，这时两个算法可能在同一道题里都要被调用。
• 分治计数题中，计算左右区间合并时，需要先用 Kadane 扫描连续段，再用阶乘逆元计算选区间的方式数量。
• 更常见的其实是周赛题单编排：T2 考数组最大连续和，T4 考模意义下的组合计数。如果你只准备了一半，就会在第二题浪费太久，导致后面没时间。

所以把它们放在一起看，并不是强行拼凑，而是因为它们代表了算法竞赛里最常用的两类“预处理思维”：一类是把大量计算结果预先算好存放，一类是用滚动状态压缩中间结果。理解了这一点，遇到题目自然能识别出该用哪种武器。

2. 阶乘逆元：模世界里的“倒数”是怎么求的

2.1 模逆元的基础概念

在实数里，a 的倒数是 1/a，满足 a·(1/a)=1。在模运算的世界里，我们同样想找一个数 b，使得 a·b ≡ 1 (mod p)。这个 b 就叫 a 的模逆元，记作 a^{-1}。

为什么需要它？因为模运算下“除以 a”没有直接对应的运算，只能用“乘以 a 的逆元”来代替。对组合数公式来说：

C(n,k) = n! / (k! · (n-k)!)

如果整个式子要对 p 取模，你没法直接算分母的模，因为 k! 和 (n-k)! 很可能包含 p 的倍数，一旦模 p 变成 0，除法就彻底失效了。处理办法是在取模之前，先把除法转换成乘法逆元。

这里有个前提：a 与 p 互质，逆元才存在。如果 p 是质数且 a 不是 p 的倍数，那就一定互质。所以竞赛题里常用的模数基本都是 1e9+7、998244353 这种大质数，目的就是为了让所有小于 p 的非零数都有逆元。

2.2 费马小定理与快速幂求逆元

费马小定理说的是：如果 p 是质数，且 a 不是 p 的倍数，那么 a^{p-1} ≡ 1 (mod p)。把等式变一下形：

a^{p-2} ≡ a^{-1} (mod p)

所以求单个数的逆元，直接算 a^{p-2} 取模就行。这看起来很简单，但 a^{p-2} 可能是个天文数字，所以要用快速幂把它在 O(log p) 时间内算出来。

我用一个非常朴素的生活类比来解释快速幂：你想算 2^10，不需要乘十次，可以先算 2^5，再自乘一次。快速幂的思想就是把指数拆成二进制，每次把底数平方，遇到当前位为 1 就乘进结果里。比如计算 x=3，p=1e9+7，那么 qpow(x, p-2) 其实只需要约 30 次乘法，远比直观的 1e9 次快得多。

long long qpow(long long a, long long b, long long mod) { long long res = 1; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } // 单点求逆元 long long inv = qpow(5, MOD - 2, MOD);

2.3 从“单点求逆元”到“批量求阶乘逆元”

如果你只需要求一两个数的组合数，用快速幂求逆元就够了。但实际题目经常会让你预处理 1 到 n 区间内的所有组合数，比如一万个查询，每个查询都单独求一次逆元，复杂度是 O(q log p)，虽然也能接受，但不够优雅。

更聪明的做法是：先预处理阶乘数组 fact，再用一次快速幂从最大的阶乘求逆，然后反向递推，一次性得到所有阶乘的逆元。

推导很简单。假设我们已经知道了 (n! )^{-1}，那么：

(n-1)! 的逆元 = n · (n! )^{-1} mod p

为什么？因为 (n! )^{-1} = 1/(n·(n-1)!) mod p，所以 (n-1)!^{-1} = n/(n!) = n · (n! )^{-1}。把这个式子倒过来写，就能从高到低逐个算出所有逆元。

同理可以反向递推得到所有阶乘的逆元：

const int MAXN = 1000000; long long fact[MAXN + 5]; long long inv_fact[MAXN + 5]; void precompute(int n, long long mod = MOD) { fact[0] = 1; for (int i = 1; i <= n; i++) { fact[i] = fact[i - 1] * i % mod; } inv_fact[n] = qpow(fact[n], mod - 2, mod); for (int i = n; i >= 1; i--) { inv_fact[i - 1] = inv_fact[i] * i % mod; } // 验证：fact[i] * inv_fact[i] % MOD == 1 }

这里有个关键的递推顺序：必须从大往小推，不能从 1 往大推。因为 inv_fact[1] 你没法直接从 fact[1] 推出来，需要逆元数组或者大阶乘反向递推。这是新手最容易写错的一点。

2.4 组合数查询代码示例

有了 fact 和 inv_fact，组合数的计算就变成了三次乘法和两次取模：

long long C(int n, int k) { if (k < 0 || k > n) return 0; return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD; }

这个 O(1) 查询可以反复用于大量组合数计算，并且不需要每次求逆元。注意参数合法性必须提前判断，否则下标越界会让你莫名其妙地 WA，而不是 RE。

2.5 递推形式与线性求逆元

除了用费马小定理，还有一种线性求逆元的方法，可以在 O(n) 时间内把 1 到 n 的所有逆元算出来。递推公式是：

inv[i] = (p - p/i) * inv[p % i] mod p

很多人第一次看到这个公式会觉得像魔法。我试着拆开讲一下：设 p = i·q + r，其中 r = p % i，且 0 < r < i。两边对 p 取模得到 i·q ≡ -r (mod p)。两边同乘 inv[i]·inv[r]，整理就得到上面这个递推公式。这个公式的好处是快，但对于 beginners 容易把 p % i 理解为普通取模，一定要在 long long 范围内运算。

有了线性逆元数组 inv[i]，阶乘逆元也可以换一种算：

inv_fact[0] = 1; for (int i = 1; i <= n; i++) { inv_fact[i] = inv_fact[i - 1] * inv[i] % MOD; }

这两种先算 inv_fact 的方式都行，实战中我更推荐用反向递推那版，因为少维护一个 inv 数组，代码更短。但如果你已经提前算好了逆元数组，用正向累乘其实更直观。

3. 最大子数组和：Kadane 算法的精髓

3.1 从暴力枚举到滚动 DP

题目描述很简单：给定整数数组 nums，找到具有最大和的连续子数组。最直接的暴力做法是枚举起点 i 和终点 j，累加 i 到 j 的和，复杂度 O(n^2)。如果再用前缀和优化，可以把内部累加变成 O(1)，但枚举起点和终点依然是 O(n^2)。

真正把复杂度降到 O(n) 的关键想法是：不要枚举终点，而是考虑“以当前位置结尾的最大子数组和”。定义：

dp[i] = 以 nums[i] 结尾的最大子数组和

那么状态转移只有两种可能：

• 只取 nums[i] 自己，也就是从 i 重新开始一段；
• 把 nums[i] 接在 dp[i-1] 后面，延续之前的子数组。

所以 dp[i] = max(nums[i], dp[i-1] + nums[i])。答案就是所有 dp[i] 里的最大值。

3.2 代码实现与负数陷阱

Kadane 算法实际上是 dp 的滚动数组版本。因为 dp[i] 只依赖 dp[i-1]，我只需要用一个局部变量 cur 来代替整个 dp 数组，再用 best 记录历史最大值。

int maxSubArray(vector<int>& nums) { int cur = 0; int best = INT_MIN; for (int x : nums) { cur = max(x, cur + x); best = max(best, cur); } return best; }

这段代码里最容易错的点是 best 的初始值。如果初始化为 0，在全负数数组里答案会错误地变成 0。因为 real answer 应该是最小的负数，比如 [-1, -2, -3] 最大子数组和是 -1，而不是 0。所以 best 必须初始化为 INT_MIN 或 nums[0]，确保它一定被第一个元素更新。

另一个常见写法是 cur = max(0, cur) + x。这个写法在 cur 非负时可以工作，但如果你把 best 初始化为 0，对于全负数数组会把空数组的和 0 当作最优解，这在允许子数组非空的问题里是错的。我的习惯是统一写成 max(x, cur + x)，然后把 best 设为 INT_MIN，杜绝这类错误。

3.3 返回子数组本身与处理空数组

很多进阶版本要求你不仅返回最大和，还要返回对应的子数组区间。做法是在更新 cur 时记录起点，更新 best 时记录终点：

int best = INT_MIN, cur = 0; int l = 0, r = 0, cur_start = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] > cur + nums[i]) { cur = nums[i]; cur_start = i; } else { cur = cur + nums[i]; } if (cur > best) { best = cur; l = cur_start; r = i; } }

对于“允许空子数组”的变体，比如 LeetCode 上有一些题要求返回空数组的和为 0，那你可以在 all negative 时单独判断。最简单的是先把最大元素拿来和 0 比较，或者允许 cur 在遇到负数时清零，最后取 max(best, 0)。

3.4 环形数组与二维矩阵的扩展

Kadane 的思维还能迁移到很多变体：

• 环形数组最大子数组和：要么子数组不跨越边界，要么跨越边界。跨越边界的那部分总和等于“数组总和减去最小子数组和”。所以先算一次 Kadane 求最大，再算一次求最小，答案就是 max(max_sum, total - min_sum)。注意全负数时 total - min_sum 可能退化成空段，需要格外判断。
• 二维矩阵最大子矩阵和：先枚举上下边界，把每一列压缩成一个数，再对压缩后的数组跑 Kadane，复杂度 O(n^3)。这个做法在竞赛里很经典，但前提是你已经吃透了最基础的一维 Kadane。

本质上，Kadane 的底层思想是“局部最优的连续段一定可以由某个起点累加而来”，这种滚动状态法不只适用于求和，也适用于最大平均子数组、最大乘积子数组等变体。你需要理解的是状态转移的推导，而不是背代码。

4. 组合起来用：实际竞赛中的细节处理

4.1 取模与负数余数的处理

两个算法放在同一道题里时，最容易出问题的其实不是算法本身，而是模运算的符号处理。C++ 对负数取模的结果是负的，比如 (-5) % MOD 在 C++ 里是负的，而数学上我们期望它是 MOD-5。所以任何可能出现负值的地方，都要先修正：

long long norm(long long x) { return (x % MOD + MOD) % MOD; }

如果你在算组合数之前先对某个数组元素取了模，可能会把原本最大的负数变成一个巨大的正数，这会让 Kadane 的判断完全失效。所以正确的流程是：先用普通整数完成 Kadane 这类最值运算，只在最终结果需要模的时候再取模。先取模再比较最值，是一个隐蔽的语义错误，我在复盘别人的代码时经常看到。

4.2 大数乘法溢出

另一个高频坑是乘法溢出。fact[i] * inv_fact[n-k] 每个值都小于 MOD=1e9+7，两个相乘大约是 1e18，刚好在 signed long long 的范围内，但如果你懒到只用 int，会在fact[n] * inv_fact[k] % MOD的瞬间溢出成负数，然后一切组合数全部算错。

我自己的习惯是：

• 所有参与取模的变量统一用 long long；
• 快速幂里的乘法也全部用 long long；
• 如果未来可能要处理更大的模数，可以考虑__int128或者蒙哥马利取模，但在竞赛环境下 long long + 1e9+7 通常已经足够。

4.3 一次预处理、多次查询的复用思维

阶乘逆元最好的使用方式是一次性预处理，调用 O(1) 查询。我在实战中的模板通常包含两个部分：

precompute(MAXN);

然后所有函数都能安全调用 C(n,k)。Kadane 则不需要预处理，它本身是线性扫描。你可以把它们放进你自己的算法模板中，在比赛开头直接precompute(200000)，后续所有组合数查询都走模板，既省心又避免每道题重复造轮子。

5. 常见问题与排查速查表

5.1 阶乘逆元相关的 WA 源头

5.2 Kadane 相关的 WA 源头

5.3 调试技巧实录

我在实际调这两个算法时，最常用的一组测试样例是：

• 全负数数组：[-1, -2, -3]能筛掉 best 初始化为 0 的错误；
• 全正数数组：[1,2,3]用来验证 Kadane 是否会正确利用累加；
• 负正交替：[-2,1,-3,4,-1,2,1,-5,4]，这是 LeetCode 的经典用例，答案应该是 6（子数组[4,-1,2,1]）；
• 组合数边界：C(0,0)、C(5,0)、C(5,5)、C(5,3)，这些手算出来都很容易验证。

如果顺带怀疑是快速幂写错，可以直接验证 qpow(2, MOD-2) 是否等于 (MOD+1)//2。计算 2 的逆元是最简单的自测。

5.4 一个我认为值得分享的实战习惯

我发现很多同学会在每次写组合数题时重新把阶乘逆元的代码敲一遍，但又不加模板管理，最后测试本地的结果是对的，交上去却因为数组长度不够而 RE。我的建议是固定一份自己的 template，把 precompute、qpow、C、norm 全部封装好，比赛时无脑调用。这样能减少很多低级失误，把脑力留给真正的难点。

Kadane 也是一样，把返回区间版本的代码存好，遇到相关变体直接改。等你能做到“看到最大子数组和就条件反射想到 cur=max(x,cur+x)”，你就已经把这类题吃透了。

6. 最后再聊点实际体会

我自己刚学这两个算法的时候，犯过一个特别傻的错误：在阶乘逆元的 precompute 里，for 循环写成for(int i=n; i>=0; i--)，然后在循环里访问inv_fact[i-1]，当 i=0 时直接下标越界。这个 bug 让我调了几十分钟，最后才发现是循环边界的问题。从那以后我固定写for(int i=n; i>=1; i--)，只在大脑里默念“从大往小安全走”。

另一个体会是，不能只是背公式。阶乘逆元的反向递推公式、Kadane 的 cur=max(x,cur+x)，这些看起来都很简单，但一旦题目换个包装，比如让你求环形数组，或者数组元素是负数且需要取模，你就会发现不理解原理的人连怎么改都不知道。真正理解状态定义和数学推导，永远比背板子重要。

这篇文章提到的内容，足够你应付绝大多数机试和竞赛场景了。如果你后续还想深入，可以再去研究线性递推逆元、Lucas 定理、二维最大子矩阵和。但先把基础模板写稳，比贪多嚼不烂更有价值。