算法这条路我见过太多人把精力花在“背模板、刷题量、看题解”上结果一到真正动手写的时候要么复杂度算错要么边界调不出来。更常见的一种现象是某道题明明有现成的数学规律代码里却硬是写成了循环枚举跑起来慢到怀疑人生。我这几年代码写下来最大的体会是——算法题里最容易被忽视的往往是那些藏得很深的数学公式。它们不声不响地躺在概率论、组合数学、数论甚至初等代数里却能在关键时刻把一道难题从 O(n²) 压到 O(n)从“超时边缘”捞回来。本文就基于“伍六七带你学算法——被忽视的数学公式”这个主题把我在实际解题、刷题和项目开发中用到过的高频数学公式拆开揉碎讲一遍适合正在备战竞赛、准备面试或者单纯想提升算法内功的开发者。我不会堆砌公式让你背而是会告诉你每个公式到底解决什么问题、在什么题型里用、推导逻辑是什么以及我在实操中踩过的坑。这些内容很多常规题解里不会写但恰恰是拉开差距的地方。1. 被忽视的数学公式决定了算法题的分水岭1.1 为什么大家会跳过数学推导先从一个我经常看到的场景说起。某次交流活动中有同学拿着一道题来找我题目大概是给一个长度为 10 万的数组要你统计所有连续子数组里满足“和能被某个数 k 整除”的数量。他说自己的思路是枚举左右端点复杂度 O(n²)数据一大就超时问我有没有什么“奇技淫巧”。我告诉他这道题本质上只用一个数学公式就能解决前缀和取模 同余计数。用(pre[i] - pre[j]) % k 0等价于pre[i] % k pre[j] % k所以只要统计每个余数出现的次数一次遍历就能算出答案。他听完之后愣了半天说“原来公式不是用来算数的是用来换思路的。”这个故事特别典型。很多人以为数学公式在算法里只是“算答案”的工具其实它真正的价值是改变问题的表达方式。你没发现这个公式就只能穷举发现了就能把问题变成哈希表计数。这就是分水岭。另外还有一个原因现在的刷题环境里大家太依赖“题解式学习”了。看到一道题先把别人的代码背下来而不是先问自己“这个解法为什么能成立” 但题解里往往只写“利用前缀和思想”背后的模运算性质却被一笔带过。于是你背会了这一题下一题换个壳又不会了。我自己的经验是数学推导能力是可以训练的而且训练性价比极高。因为数学公式是通用的一个公式理解了能辐射到几十道题而一个代码模板理解了只能覆盖同类题。这也是为什么我越来越重视公式底层逻辑的原因。1.2 一张表看清哪些公式最该补按照我在实际刷题和项目里遇到的频率我把“值得专门花时间搞懂”的公式分成了几个梯队公式/模型核心价值典型应用场景模运算三律与逆元避免溢出、支持大数据取模组合数取模、大数运算、哈希前缀和与差分区间操作从 O(n) 降到 O(1)区间求和、区间修改、二维矩阵操作等比/等差求和公式快速计算规律数列分治递归、动态规划优化卡特兰数统一计数模型括号序列、出入栈、二叉树计数二项式系数/组合数排列组合计数基础概率题、组合优化、动态规划特征方程/递推转通项递推关系一步算到底斐波那契数列、矩阵快速幂几何分布/全期望公式计算随机过程期望概率题、抽卡期望、队列估算容斥原理处理“至少/恰好”计数错排问题、集合覆盖计数位运算的数学内核常数级优化、状态压缩奇偶判断、2 的幂判定、树状数组这张表里的每一项我都见过它在真实题目里“卡人”。比如卡特兰数很多人只是听说过名字但真遇到“给定 n 个节点能组成多少种不同的二叉树”时却完全联系不上。数学公式的价值不在于记忆而在于识别——你能认出题目场景属于哪个数学模型就已经赢了一半。2. 模运算与前缀和把高频问题压成常数级操作2.1 模运算三铁律模运算应该是算法里最常用、也最容易被忽视的数学公式了。我在代码 review 里不止一次看到有人写出类似这样的代码long long ans 1; for (int i 1; i n; i) { ans ans * i % MOD; // 这样做是对的 }但在更复杂的场景里比如计算组合数C(n, k) % MOD很多人会第一时间想到先算出真正的组合数再去取模。这就有两个问题第一组合数可能巨大无比long long 根本装不下第二即便用大数库运算效率也低得离谱。这时候就需要模运算的“三铁律”加法取模(a b) % MOD ((a % MOD) (b % MOD)) % MOD减法取模(a - b) % MOD ((a % MOD) - (b % MOD) MOD) % MOD乘法取模(a * b) % MOD ((a % MOD) * (b % MOD)) % MOD这三条是保命的。因为它意味着你可以在每一步运算之后都取模而不需要等最终结果出来。这样不仅不会溢出还能让中间数据一直保持在可处理范围内。但除法不行。(a / b) % MOD不能直接拆成(a % MOD) / (b % MOD)这在数学上不成立。比如(6 / 2) % 5 3 % 5 3但如果拆开算6 % 5 12 % 5 21 / 2等于 0完全是错的。解决除法取模问题的标准做法是求模逆元。简单说如果MOD是质数根据费马小定理a^(MOD-2) % MOD就是a在模 MOD 意义下的逆元也就是说b * b^(MOD-2) ≡ 1 (mod MOD)。于是(a / b) % MOD可以转换成(a % MOD) * (b^(MOD-2) % MOD) % MOD。我举一个真实用到的例子。有一道组合计数的题要求计算C(n, k) % (10^9 7)n 最大到 10^6。如果你老老实实用递推公式C(n, k) C(n-1, k) C(n-1, k-1)打表空间和时间都是 O(n²)直接炸掉。正确做法是预计算阶乘数组fact[i]和阶乘逆元inv_fact[i]然后用公式C(n, k) fact[n] * inv_fact[k] * inv_fact[n-k] % MOD一次算出答案。这背后全是模运算三铁律和费马小定理在支撑。注意求逆元的前提是模数为质数。如果模数不是质数比如MOD 1000000008费马小定理不成立就得换用扩展欧几里得来求逆元。我在初学阶段踩过这个坑后来养成习惯第一件事先看模数是不是质数。2.2 前缀和与差分把区间问题从遍历变成公式前缀和并不是一个多么高深的数学公式但它背后有一条非常朴素的思想用预处理换取查询时间。一维前缀和的定义是pre[i] pre[i-1] a[i]。一旦有了pre数组求区间[l, r]的和就不是遍历了而是直接用pre[r] - pre[l-1]时间复杂度 O(1)。这个公式的推导很简单但它的应用价值被很多人低估了。比如前面提到的“子数组和能被 k 整除”问题本质上是在所有i j里面统计(pre[j] - pre[i]) % k 0的数量。利用pre[j] % k pre[i] % k这个等价变换你只需要维护一个cnt数组记录每个余数出现了几次。遍历到某一个位置时看前面相同余数出现了多少次累加即可。这个技巧我在多道“连续子数组”题里用过实测下来非常稳。二维前缀和的公式更值得单独写一笔。它在矩阵场景中用来快速求子矩阵和公式是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]很多人背这个公式时觉得绕其实它的逻辑特别直观要算S[i][j]先加上上方区域和左方区域但左上角那块S[i-1][j-1]被加了两次所以要减掉一次最后再加上当前格子本身。这就是一个简单的容斥思想。反过来差分数组则是前缀和的逆运算。它的核心公式是对于区间[l, r]加上一个值v只需要diff[l] vdiff[r1] - v最后对差分数组做一次前缀和就能还原出每个位置的值。这个技巧在“多次区间修改最后统一查询”的场景里是杀手锏复杂度直接从 O(nm) 降到 O(nm)。2.3 等比数列求和与二分递归等比数列求和公式本身是高中数学内容S_n a * (1 - q^n) / (1 - q)。但把它用在算法里就有一个容易被忽视的坑如果要求S_n % MOD分母(1 - q)不能直接除得先求它的模逆元再乘。这是我早期经常出错的地方。还有一个更隐蔽的场景当需要计算一个非常长的等比数列和但项数大到连q^n都算不动时可以用二分递归的方式。具体思路是sum(n) sum(n/2) q^(n/2) * sum(n/2)配快速幂可以在 O(log n) 时间内算出任意长度的等比数列和。我记得有一道分治题要求计算一个矩阵的幂级数求和比如E A A^2 ... A^k。如果不知道等比数列公式和二分递归就只能老老实实算 k 次矩阵乘法k 一旦到 10^9 就直接超时。但用二分递归每一层只需要做常数次矩阵乘法总复杂度立刻降到 O(log k · n^3)。这个优化思路在很多“矩阵快速幂”的变体题里都是关键。我个人的建议是等比数列求和公式不要只记标准形式要把它和“矩阵、多项式、模运算”结合起来理解。因为一旦你接受了“求和公式可以泛化到非数值对象”这个观念很多奇奇怪怪的题就都有了下手点。3. 组合计数里的定海神针卡特兰数、二项式系数与递推通项3.1 卡特兰数不是一个公式是一个计数模型家族卡特兰数大概是“听过名字但没真正理解”的公式榜首。它的定义是h(0) 1 h(n) h(0)*h(n-1) h(1)*h(n-2) ... h(n-1)*h(0)通项公式则是h(n) C(2n, n) / (n 1)我第一次接触它时也觉得这只是又一个需要背的公式。直到我在一道“n 对括号能组成多少种合法括号序列”的题里试着手动枚举了 n3 的情况后才发现卡特兰数的递推式其实就是枚举第一个右括号的位置。具体来说假设我们要数 n 对括号的合法序列。考虑第一个右括号出现在第2k个位置也就是它匹配了前面的某个左括号此时这个右括号左边有 k 对合法括号右边有 n-1-k 对合法括号。于是总数就是所有 k 从 0 到 n-1 的和。这就是卡特兰数递推式的直观来源。一旦理解了这一层卡特兰数的应用范围就完全打开了计数问题对应的卡特兰数模型n 对括号的合法序列数量h(n)n 个节点能组成多少种不同的二叉树h(n)n 个元素入栈出栈的合法序列数h(n)n 个矩阵相乘的加括号方式数h(n-1)我后来遇到一道题要求数“n 个节点的二叉树有多少种形态”如果没有卡特兰数纯靠 DFS 根本不可能在 n1000 时算出来。但知道了它属于卡特兰数模型直接套通项公式取模之后一行代码搞定。这真的不是玄学而是模型识别的胜利。实操提醒当 n 较大比如 10^6直接算C(2n, n)/(n1)时除法取模一定要求逆元。还记得前面说的模运算吗这里就是综合应用的好例子。3.2 二项式系数的两种提速姿势二项式系数C(n, k)是组合计数的基础。它在算法题里的出场率极高——概率题、排列组合题、动态规划优化、生成函数全都绕不开它。第一种提速姿势是递推表。利用帕斯卡法则C(n, k) C(n-1, k-1) C(n-1, k)可以在 O(n²) 时间内预处理出所有组合数。这种方式适合 n 比较小比如 n ≤ 2000且需要多次查询的场景。第二种提速姿势是阶乘逆元。当 n 很大比如 n ≤ 10^6时O(n²) 的递推表根本开不下。此时应先算fact[i]和inv_fact[i]再利用C(n, k) fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD直接 O(1) 查询。这个方案的前提是模数为质数这样可以借助费马小定理来求逆元。这两种姿势我有过非常惨痛的教训。有次写概率 DP状态定义里需要多次调用组合数。我一开始图省事用递归方式现算C(n, k)结果同一个组合数被反复计算了几百万次直接超时到怀疑人生。后来改成预计算整个程序从 30 秒优化到 2 秒。自那以后我形成一条铁律凡是需要在循环里多次用到的组合数一律预计算。3.3 从递推到通项斐波那契与矩阵快速幂递推公式转通项公式是很多人觉得“数学太难”的章节但它恰恰是优化动态规划的一把钥匙。以斐波那契数列为例标准递推是f(n) f(n-1) f(n-2)。如果不加思考扛着这个递推式一路算到 n10^18就算用上记忆化也救不了你——因为你需要存 10^18 个状态。但如果你把递推写成矩阵形式[f(n)] [1 1] ^ (n-1) [f(1)] [f(n-1)] [1 0] * [f(0)]就能用矩阵快速幂在 O(log n) 时间内算出第 n 项。这个思路的本质是线性递推关系可以用矩阵乘法来“批量推进”而矩阵乘法本身满足结合律所以能用快速幂加速。我在一道“爬楼梯变种题”里用过这个方法。题目规定你一次可以跨 1 级或 2 级台阶但第 n 级不能踩要求方案数。这其实就是斐波那契的变形只是多了几个特殊状态而已。利用矩阵快速幂和特征方程可以把看似复杂的方案数计算变成一行公式。更一般地对于形如f(n) a*f(n-1) b*f(n-2)的二阶线性递推其特征方程为x^2 a*x b。解出两个特征根 r1、r2 后通项就是f(n) A*r1^n B*r2^n。如果你在题里看到“n 高达 10^9 的递推计算”第一时间就该想到矩阵快速幂或特征方程而不是老老实实循环。4. 概率、期望和位运算背后往往就是一行公式的事4.1 几何分布与全期望先算“一步的代价”概率题在算法面试里不算特别多但一旦出现很多人就懵了。我去看过一些同学写概率题的过程最大的问题不是不会算而是不知道从哪里下手。其实概率题有一个偷懒的入口先找“一步的代价”。举个最常见的模型掷一枚硬币正面朝上的概率是 p问“第一次出现正面需要掷多少次”的期望次数是多少如果你直觉上认为答案是 “1/p次”那么恭喜你你已经会用几何分布公式了。更正式地几何分布的期望是E(X) 1 / p这个公式在抽卡游戏里太常见了。假设某张卡的掉率是 1%那么期望抽数就是 100 次。虽然实际体验中你可能抽 300 次才出但在期望值上确实是 100 次。理解这个公式能帮你在一道题里快速排除错误选项不用每一步都从头推导。再进一步全期望公式E(X) E[E(X|Y)]是解决复杂期望问题的利器。它的白话理解是如果事件可以按某种条件分组那总期望等于每组期望按概率加权平均。我举一个简单的例子。假设随机过程是先等概率选择一种颜色红或蓝然后按照所选颜色对应的几何分布红: p1/2蓝: p1/3不断抽奖直到成功。问期望抽数是多少用全期望公式两行就能算完E 0.5 * (1 / 0.5) 0.5 * (1 / 0.333...) 0.5*2 0.5*3 2.5。这个思路在“随机过程分层”的题目里特别好用尤其适合处理“先选分支再跑独立实验”的模型。我的习惯是遇到期望题先在草稿纸上写出“每一步可能的代价”和“对应概率”然后再套全期望公式或几何分布。大多数看似复杂的概率题拆到这一步基本就通透了。4.2 容斥原理减多了别慌加上再减容斥原理在算法题里出场率极高尤其在计数类问题里。公式写出来很简单|A∪B∪C| |A| |B| |C| - |A∩B| - |A∩C| - |B∩C| |A∩B∩C|但它的厉害之处在于能处理“至少满足一个条件”或者“恰好满足某个条件”的计数问题。举个我在练习题里遇到的经典场景给定 1 到 n 的排列要求计算“至少有一个人站在自己编号位置”的排列数。如果直接枚举“哪些人站在自己的位置”会陷入重复计数。但用容斥原理可以先算“恰好所有人都错排”的情况——也就是错排公式D(n) (n-1) * (D(n-1) D(n-2))再拿全排列减去错排数量就得到了“至少一人没动”的答案。容斥原理还有一个典型应用是算“区间内能被至少一个数整除的整数个数”。如果枚举因子集合是 {2, 3, 5}那就可以用容斥公式展开先把能被 2、3、5 整除的数量分别加进来再减去能被 2×3、2×5、3×5 整除的数量最后加上能被 2×3×5 整除的数量。每一步都是一行公式的事完全不用暴力枚举每个整数。实操中要注意当集合里有重复因子时容斥展开每一项的系数是 (-1)^k其中 k 是当前子集的大小。我写这类题时习惯用位运算枚举子集这样代码自然、不容易漏项。4.3 位运算的数学内核奇偶、异或与低位提取位运算看起来像是“代码技巧”但它的底层全是数学公式。理解了数学原理你就不会再把位运算当成“一堆奇怪的符号”来背了。n 1等价于判断 n 是否为奇数因为它只取二进制最低位。n (n-1)可以用来去掉二进制表示中最低位的 1所以n (n-1) 0等价于 n 是 2 的幂。x (-x)提取最低位的 1。-x在二进制补码下是~x 1按位与之后就能拿到最低位的那个 1。异或运算满足交换律和结合律且a ^ a 0a ^ 0 a。这导出了一个经典公式一组数中只有一个是单个出现的其余都成对出现找出那个单数只需要把所有数异或起来结果就是答案。这些不只是面试题里的“奇技淫巧”在树状数组、状态压缩动态规划、哈希散列里它们都是基础设施。尤其x (-x)在树状数组里就是核心操作每次从某个节点向上回溯时都要用它来找到父节点。我见过很多人在树状数组代码里死记x x (-x)和x - x (-x)一旦问起为什么是这个式子就说不清楚。其实搞懂了补码和按位与的数学原理这两个式子自然就“长”在脑子里了。5. 刷题实战中的高频事故与公式速查5.1 五大翻车现场实录数学公式在实战中并不总是一步到位相反我见过太多人在“最后一步”翻车。这里整理几个我亲身经历过的典型事故你可以对照着避坑。事故一忘记对负数取模取模的结果在大多数编程语言里可能带符号。比如(-5) % 3在 C 里的结果是 -2不是 2。如果你拿着这个负数直接去当数组下标或者计数得到的答案一定是错的。解决方式是统一加模数再取模((x % MOD) MOD) % MOD。这个习惯我养成之后再也没在负数取模上吃过亏。事故二除法取模直接做除法前面说过模意义下不能直接做除法。有一次我写组合数公式偷懒直接在表达式里写成C(2n, n) / (n1)结果对小数据全部正确一上大数据就开始乱飘。排查半天才发现是忘记求逆元。从那以后我在代码里看到“斜杠”就会条件反射地警觉。事故三浮点数比较用等号算几何类题目时有时候需要判断两个浮点数是否相等。如果直接用double a double b多半会在精度上翻车。正确做法是加一个误差范围fabs(a - b) 1e-9。这个教训来自一次面积计算题因为直接比较导致判题系统一直报错。事故四预处理数组没开 long long前缀和、差分数组在 n 很大时中间值可能超过 int 范围。我在一道二维矩阵题里因为偷懒用int存前缀和结果一上大规模数据就溢出答案全部变成负数。后来所有涉及累加的预处理数组一律用long long这个习惯帮我避开了一大批隐蔽 bug。事故五递推式的初始条件写错卡特兰数、错排公式、斐波那契这些递推关系边界条件一旦写错整个数列就全都偏了。我常用的自查办法是先手动算前几项比如 n0、1、2、3和题目样例或已知结论做对比确认无误后再放心递推。这个“小数据验证”的习惯值得刻在脑子里。我把这些事故整理成了速查表问题常见表现解决思路负数取模答案莫名比预期小((x % MOD) MOD) % MOD除法取模大数据错误、小数据正确用费马小定理或扩展欧几里得求逆元浮点比较用比较误差大用fabs(a-b) eps判断数据溢出答案变成负数预处理数组用long long边界条件错误小数据就不对先手算几个小项验证5.2 建立公式直觉的三个日常习惯公式不是考前突击就能掌握的它需要在日常刷题中不断积累。我总结了三个对我特别有用的习惯你可以直接拿去用。第一个习惯拿到题先看数据范围再动手。如果题目给的 n 是 10^5 甚至 10^9说明它大概率不是让你暴力枚举的。这时候我会停下来想一想这个规模下有哪些数学工具能用是前缀和是矩阵快速幂还是容斥原理数据范围本身就在暗示你该用哪个公式。第二个习惯把公式当成“解题关键词”来复盘。每次做完一道题我会在笔记里写清楚“这道题用到哪个公式、为什么这个公式能切入、还有哪些题属于同一类模型”。这样做的好处是当你之后再遇到类似的题目时大脑会不由自主地跳出那个公式。我从“看到数对括号想枚举”到“看到数对括号直接想到卡特兰数”就是靠这个复盘习惯实现的。第三个习惯别光看题解亲手推导一遍。就算只是三行的推导也要在草稿纸上写出来。因为看题解是“别人告诉你结果”手推才是“自己验证因果”。我在理解二维前缀和公式时一开始也是懵的但当我画了一个 3×3 的矩阵把每个区域都标出来之后那个容斥公式就再也不会记混了。5.3 公式速查小抄最后送上一份精简版速查小抄建议收藏备用。它不能替代理解但能在你卡壳的时候给你一个支点。公式表达式使用提醒一维前缀和pre[i] pre[i-1] a[i]区间和 pre[r] - pre[l-1]二维前缀和S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]注意左上角被减两次等比数列求和S_n a*(1-q^n)/(1-q)取模时用逆元处理分母卡特兰数h(n) C(2n, n)/(n1)n 大时记得求逆元组合数(O(1)查询)C(n, k) fact[n]*inv_fact[k]*inv_fact[n-k]需要预计算阶乘和逆元几何分布期望E 1/p适用于首次成功实验容斥原理加单集合减两两交集加三三交集每一项系数是 (-1)^k错排公式D(n) (n-1)*(D(n-1)D(n-2))初始条件D(0)1, D(1)0最低位 1x (-x)树状数组、二进枚举常用2 的幂判定n (n-1) 0记得单独处理 n06. 我的一点私房心得公式是用来推导的不是用来背的写到这里我想再说一件比公式本身更重要的事。我在带新人时经常说一句话公式是理解问题的结果而不是解决问题的起点。如果你只是背下了卡特兰数的通项公式而不知道它的递推式来自“枚举第一个右括号的位置”那么题目稍微变形你就又会被卡住。我自己有个小方法每次遇到一个陌生公式先花十分钟亲手推一遍。哪怕推不出来只推一半也比完全不推强。因为推导过程会逼你去关注“这个公式为什么长这样”而不是把公式当成一个黑盒。很多看起来唬人的公式拆开之后都只是一层窗户纸。另外我强烈建议你在刷题时准备一个“公式触发清单”。比如“见到连续区间、子数组、和/差”——想前缀和、差分、哈希。“见到 n 巨大、递推关系”——想矩阵快速幂、特征方程。“见到括号序列、出入栈、二叉树计数”——想卡特兰数。“见到排列、子集、计数”——想容斥、组合数、错排。“见到概率、期望”——想几何分布、全期望。这个清单看起来简单但它能帮你在考场上快速建立“数学图示”而不是陷入盲目试代码的泥潭。我个人在实际操作中最深的体会是算法题的最高分水岭往往不在代码而在数学上的选择。同一个问题用不同的公式去描述复杂度可能是天差地别。所以与其疯狂刷题比你多写了多少行代码不如在每道题结束之后多问自己一句“这道题背后的数学公式是什么”你把这个习惯坚持下去会发现那些曾经让你头疼的公式慢慢都变成了解题时最顺手的武器。至少在“伍六七带你学算法”这条路上我能看到的最快的成长路径就是先搞定这群被忽视的数学公式。
算法这条路我见过太多人把精力花在“背模板、刷题量、看题解”上结果一到真正动手写的时候要么复杂度算错要么边界调不出来。更常见的一种现象是某道题明明有现成的数学规律代码里却硬是写成了循环枚举跑起来慢到怀疑人生。我这几年代码写下来最大的体会是——算法题里最容易被忽视的往往是那些藏得很深的数学公式。它们不声不响地躺在概率论、组合数学、数论甚至初等代数里却能在关键时刻把一道难题从 O(n²) 压到 O(n)从“超时边缘”捞回来。本文就基于“伍六七带你学算法——被忽视的数学公式”这个主题把我在实际解题、刷题和项目开发中用到过的高频数学公式拆开揉碎讲一遍适合正在备战竞赛、准备面试或者单纯想提升算法内功的开发者。我不会堆砌公式让你背而是会告诉你每个公式到底解决什么问题、在什么题型里用、推导逻辑是什么以及我在实操中踩过的坑。这些内容很多常规题解里不会写但恰恰是拉开差距的地方。1. 被忽视的数学公式决定了算法题的分水岭1.1 为什么大家会跳过数学推导先从一个我经常看到的场景说起。某次交流活动中有同学拿着一道题来找我题目大概是给一个长度为 10 万的数组要你统计所有连续子数组里满足“和能被某个数 k 整除”的数量。他说自己的思路是枚举左右端点复杂度 O(n²)数据一大就超时问我有没有什么“奇技淫巧”。我告诉他这道题本质上只用一个数学公式就能解决前缀和取模 同余计数。用(pre[i] - pre[j]) % k 0等价于pre[i] % k pre[j] % k所以只要统计每个余数出现的次数一次遍历就能算出答案。他听完之后愣了半天说“原来公式不是用来算数的是用来换思路的。”这个故事特别典型。很多人以为数学公式在算法里只是“算答案”的工具其实它真正的价值是改变问题的表达方式。你没发现这个公式就只能穷举发现了就能把问题变成哈希表计数。这就是分水岭。另外还有一个原因现在的刷题环境里大家太依赖“题解式学习”了。看到一道题先把别人的代码背下来而不是先问自己“这个解法为什么能成立” 但题解里往往只写“利用前缀和思想”背后的模运算性质却被一笔带过。于是你背会了这一题下一题换个壳又不会了。我自己的经验是数学推导能力是可以训练的而且训练性价比极高。因为数学公式是通用的一个公式理解了能辐射到几十道题而一个代码模板理解了只能覆盖同类题。这也是为什么我越来越重视公式底层逻辑的原因。1.2 一张表看清哪些公式最该补按照我在实际刷题和项目里遇到的频率我把“值得专门花时间搞懂”的公式分成了几个梯队公式/模型核心价值典型应用场景模运算三律与逆元避免溢出、支持大数据取模组合数取模、大数运算、哈希前缀和与差分区间操作从 O(n) 降到 O(1)区间求和、区间修改、二维矩阵操作等比/等差求和公式快速计算规律数列分治递归、动态规划优化卡特兰数统一计数模型括号序列、出入栈、二叉树计数二项式系数/组合数排列组合计数基础概率题、组合优化、动态规划特征方程/递推转通项递推关系一步算到底斐波那契数列、矩阵快速幂几何分布/全期望公式计算随机过程期望概率题、抽卡期望、队列估算容斥原理处理“至少/恰好”计数错排问题、集合覆盖计数位运算的数学内核常数级优化、状态压缩奇偶判断、2 的幂判定、树状数组这张表里的每一项我都见过它在真实题目里“卡人”。比如卡特兰数很多人只是听说过名字但真遇到“给定 n 个节点能组成多少种不同的二叉树”时却完全联系不上。数学公式的价值不在于记忆而在于识别——你能认出题目场景属于哪个数学模型就已经赢了一半。2. 模运算与前缀和把高频问题压成常数级操作2.1 模运算三铁律模运算应该是算法里最常用、也最容易被忽视的数学公式了。我在代码 review 里不止一次看到有人写出类似这样的代码long long ans 1; for (int i 1; i n; i) { ans ans * i % MOD; // 这样做是对的 }但在更复杂的场景里比如计算组合数C(n, k) % MOD很多人会第一时间想到先算出真正的组合数再去取模。这就有两个问题第一组合数可能巨大无比long long 根本装不下第二即便用大数库运算效率也低得离谱。这时候就需要模运算的“三铁律”加法取模(a b) % MOD ((a % MOD) (b % MOD)) % MOD减法取模(a - b) % MOD ((a % MOD) - (b % MOD) MOD) % MOD乘法取模(a * b) % MOD ((a % MOD) * (b % MOD)) % MOD这三条是保命的。因为它意味着你可以在每一步运算之后都取模而不需要等最终结果出来。这样不仅不会溢出还能让中间数据一直保持在可处理范围内。但除法不行。(a / b) % MOD不能直接拆成(a % MOD) / (b % MOD)这在数学上不成立。比如(6 / 2) % 5 3 % 5 3但如果拆开算6 % 5 12 % 5 21 / 2等于 0完全是错的。解决除法取模问题的标准做法是求模逆元。简单说如果MOD是质数根据费马小定理a^(MOD-2) % MOD就是a在模 MOD 意义下的逆元也就是说b * b^(MOD-2) ≡ 1 (mod MOD)。于是(a / b) % MOD可以转换成(a % MOD) * (b^(MOD-2) % MOD) % MOD。我举一个真实用到的例子。有一道组合计数的题要求计算C(n, k) % (10^9 7)n 最大到 10^6。如果你老老实实用递推公式C(n, k) C(n-1, k) C(n-1, k-1)打表空间和时间都是 O(n²)直接炸掉。正确做法是预计算阶乘数组fact[i]和阶乘逆元inv_fact[i]然后用公式C(n, k) fact[n] * inv_fact[k] * inv_fact[n-k] % MOD一次算出答案。这背后全是模运算三铁律和费马小定理在支撑。注意求逆元的前提是模数为质数。如果模数不是质数比如MOD 1000000008费马小定理不成立就得换用扩展欧几里得来求逆元。我在初学阶段踩过这个坑后来养成习惯第一件事先看模数是不是质数。2.2 前缀和与差分把区间问题从遍历变成公式前缀和并不是一个多么高深的数学公式但它背后有一条非常朴素的思想用预处理换取查询时间。一维前缀和的定义是pre[i] pre[i-1] a[i]。一旦有了pre数组求区间[l, r]的和就不是遍历了而是直接用pre[r] - pre[l-1]时间复杂度 O(1)。这个公式的推导很简单但它的应用价值被很多人低估了。比如前面提到的“子数组和能被 k 整除”问题本质上是在所有i j里面统计(pre[j] - pre[i]) % k 0的数量。利用pre[j] % k pre[i] % k这个等价变换你只需要维护一个cnt数组记录每个余数出现了几次。遍历到某一个位置时看前面相同余数出现了多少次累加即可。这个技巧我在多道“连续子数组”题里用过实测下来非常稳。二维前缀和的公式更值得单独写一笔。它在矩阵场景中用来快速求子矩阵和公式是S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]很多人背这个公式时觉得绕其实它的逻辑特别直观要算S[i][j]先加上上方区域和左方区域但左上角那块S[i-1][j-1]被加了两次所以要减掉一次最后再加上当前格子本身。这就是一个简单的容斥思想。反过来差分数组则是前缀和的逆运算。它的核心公式是对于区间[l, r]加上一个值v只需要diff[l] vdiff[r1] - v最后对差分数组做一次前缀和就能还原出每个位置的值。这个技巧在“多次区间修改最后统一查询”的场景里是杀手锏复杂度直接从 O(nm) 降到 O(nm)。2.3 等比数列求和与二分递归等比数列求和公式本身是高中数学内容S_n a * (1 - q^n) / (1 - q)。但把它用在算法里就有一个容易被忽视的坑如果要求S_n % MOD分母(1 - q)不能直接除得先求它的模逆元再乘。这是我早期经常出错的地方。还有一个更隐蔽的场景当需要计算一个非常长的等比数列和但项数大到连q^n都算不动时可以用二分递归的方式。具体思路是sum(n) sum(n/2) q^(n/2) * sum(n/2)配快速幂可以在 O(log n) 时间内算出任意长度的等比数列和。我记得有一道分治题要求计算一个矩阵的幂级数求和比如E A A^2 ... A^k。如果不知道等比数列公式和二分递归就只能老老实实算 k 次矩阵乘法k 一旦到 10^9 就直接超时。但用二分递归每一层只需要做常数次矩阵乘法总复杂度立刻降到 O(log k · n^3)。这个优化思路在很多“矩阵快速幂”的变体题里都是关键。我个人的建议是等比数列求和公式不要只记标准形式要把它和“矩阵、多项式、模运算”结合起来理解。因为一旦你接受了“求和公式可以泛化到非数值对象”这个观念很多奇奇怪怪的题就都有了下手点。3. 组合计数里的定海神针卡特兰数、二项式系数与递推通项3.1 卡特兰数不是一个公式是一个计数模型家族卡特兰数大概是“听过名字但没真正理解”的公式榜首。它的定义是h(0) 1 h(n) h(0)*h(n-1) h(1)*h(n-2) ... h(n-1)*h(0)通项公式则是h(n) C(2n, n) / (n 1)我第一次接触它时也觉得这只是又一个需要背的公式。直到我在一道“n 对括号能组成多少种合法括号序列”的题里试着手动枚举了 n3 的情况后才发现卡特兰数的递推式其实就是枚举第一个右括号的位置。具体来说假设我们要数 n 对括号的合法序列。考虑第一个右括号出现在第2k个位置也就是它匹配了前面的某个左括号此时这个右括号左边有 k 对合法括号右边有 n-1-k 对合法括号。于是总数就是所有 k 从 0 到 n-1 的和。这就是卡特兰数递推式的直观来源。一旦理解了这一层卡特兰数的应用范围就完全打开了计数问题对应的卡特兰数模型n 对括号的合法序列数量h(n)n 个节点能组成多少种不同的二叉树h(n)n 个元素入栈出栈的合法序列数h(n)n 个矩阵相乘的加括号方式数h(n-1)我后来遇到一道题要求数“n 个节点的二叉树有多少种形态”如果没有卡特兰数纯靠 DFS 根本不可能在 n1000 时算出来。但知道了它属于卡特兰数模型直接套通项公式取模之后一行代码搞定。这真的不是玄学而是模型识别的胜利。实操提醒当 n 较大比如 10^6直接算C(2n, n)/(n1)时除法取模一定要求逆元。还记得前面说的模运算吗这里就是综合应用的好例子。3.2 二项式系数的两种提速姿势二项式系数C(n, k)是组合计数的基础。它在算法题里的出场率极高——概率题、排列组合题、动态规划优化、生成函数全都绕不开它。第一种提速姿势是递推表。利用帕斯卡法则C(n, k) C(n-1, k-1) C(n-1, k)可以在 O(n²) 时间内预处理出所有组合数。这种方式适合 n 比较小比如 n ≤ 2000且需要多次查询的场景。第二种提速姿势是阶乘逆元。当 n 很大比如 n ≤ 10^6时O(n²) 的递推表根本开不下。此时应先算fact[i]和inv_fact[i]再利用C(n, k) fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD直接 O(1) 查询。这个方案的前提是模数为质数这样可以借助费马小定理来求逆元。这两种姿势我有过非常惨痛的教训。有次写概率 DP状态定义里需要多次调用组合数。我一开始图省事用递归方式现算C(n, k)结果同一个组合数被反复计算了几百万次直接超时到怀疑人生。后来改成预计算整个程序从 30 秒优化到 2 秒。自那以后我形成一条铁律凡是需要在循环里多次用到的组合数一律预计算。3.3 从递推到通项斐波那契与矩阵快速幂递推公式转通项公式是很多人觉得“数学太难”的章节但它恰恰是优化动态规划的一把钥匙。以斐波那契数列为例标准递推是f(n) f(n-1) f(n-2)。如果不加思考扛着这个递推式一路算到 n10^18就算用上记忆化也救不了你——因为你需要存 10^18 个状态。但如果你把递推写成矩阵形式[f(n)] [1 1] ^ (n-1) [f(1)] [f(n-1)] [1 0] * [f(0)]就能用矩阵快速幂在 O(log n) 时间内算出第 n 项。这个思路的本质是线性递推关系可以用矩阵乘法来“批量推进”而矩阵乘法本身满足结合律所以能用快速幂加速。我在一道“爬楼梯变种题”里用过这个方法。题目规定你一次可以跨 1 级或 2 级台阶但第 n 级不能踩要求方案数。这其实就是斐波那契的变形只是多了几个特殊状态而已。利用矩阵快速幂和特征方程可以把看似复杂的方案数计算变成一行公式。更一般地对于形如f(n) a*f(n-1) b*f(n-2)的二阶线性递推其特征方程为x^2 a*x b。解出两个特征根 r1、r2 后通项就是f(n) A*r1^n B*r2^n。如果你在题里看到“n 高达 10^9 的递推计算”第一时间就该想到矩阵快速幂或特征方程而不是老老实实循环。4. 概率、期望和位运算背后往往就是一行公式的事4.1 几何分布与全期望先算“一步的代价”概率题在算法面试里不算特别多但一旦出现很多人就懵了。我去看过一些同学写概率题的过程最大的问题不是不会算而是不知道从哪里下手。其实概率题有一个偷懒的入口先找“一步的代价”。举个最常见的模型掷一枚硬币正面朝上的概率是 p问“第一次出现正面需要掷多少次”的期望次数是多少如果你直觉上认为答案是 “1/p次”那么恭喜你你已经会用几何分布公式了。更正式地几何分布的期望是E(X) 1 / p这个公式在抽卡游戏里太常见了。假设某张卡的掉率是 1%那么期望抽数就是 100 次。虽然实际体验中你可能抽 300 次才出但在期望值上确实是 100 次。理解这个公式能帮你在一道题里快速排除错误选项不用每一步都从头推导。再进一步全期望公式E(X) E[E(X|Y)]是解决复杂期望问题的利器。它的白话理解是如果事件可以按某种条件分组那总期望等于每组期望按概率加权平均。我举一个简单的例子。假设随机过程是先等概率选择一种颜色红或蓝然后按照所选颜色对应的几何分布红: p1/2蓝: p1/3不断抽奖直到成功。问期望抽数是多少用全期望公式两行就能算完E 0.5 * (1 / 0.5) 0.5 * (1 / 0.333...) 0.5*2 0.5*3 2.5。这个思路在“随机过程分层”的题目里特别好用尤其适合处理“先选分支再跑独立实验”的模型。我的习惯是遇到期望题先在草稿纸上写出“每一步可能的代价”和“对应概率”然后再套全期望公式或几何分布。大多数看似复杂的概率题拆到这一步基本就通透了。4.2 容斥原理减多了别慌加上再减容斥原理在算法题里出场率极高尤其在计数类问题里。公式写出来很简单|A∪B∪C| |A| |B| |C| - |A∩B| - |A∩C| - |B∩C| |A∩B∩C|但它的厉害之处在于能处理“至少满足一个条件”或者“恰好满足某个条件”的计数问题。举个我在练习题里遇到的经典场景给定 1 到 n 的排列要求计算“至少有一个人站在自己编号位置”的排列数。如果直接枚举“哪些人站在自己的位置”会陷入重复计数。但用容斥原理可以先算“恰好所有人都错排”的情况——也就是错排公式D(n) (n-1) * (D(n-1) D(n-2))再拿全排列减去错排数量就得到了“至少一人没动”的答案。容斥原理还有一个典型应用是算“区间内能被至少一个数整除的整数个数”。如果枚举因子集合是 {2, 3, 5}那就可以用容斥公式展开先把能被 2、3、5 整除的数量分别加进来再减去能被 2×3、2×5、3×5 整除的数量最后加上能被 2×3×5 整除的数量。每一步都是一行公式的事完全不用暴力枚举每个整数。实操中要注意当集合里有重复因子时容斥展开每一项的系数是 (-1)^k其中 k 是当前子集的大小。我写这类题时习惯用位运算枚举子集这样代码自然、不容易漏项。4.3 位运算的数学内核奇偶、异或与低位提取位运算看起来像是“代码技巧”但它的底层全是数学公式。理解了数学原理你就不会再把位运算当成“一堆奇怪的符号”来背了。n 1等价于判断 n 是否为奇数因为它只取二进制最低位。n (n-1)可以用来去掉二进制表示中最低位的 1所以n (n-1) 0等价于 n 是 2 的幂。x (-x)提取最低位的 1。-x在二进制补码下是~x 1按位与之后就能拿到最低位的那个 1。异或运算满足交换律和结合律且a ^ a 0a ^ 0 a。这导出了一个经典公式一组数中只有一个是单个出现的其余都成对出现找出那个单数只需要把所有数异或起来结果就是答案。这些不只是面试题里的“奇技淫巧”在树状数组、状态压缩动态规划、哈希散列里它们都是基础设施。尤其x (-x)在树状数组里就是核心操作每次从某个节点向上回溯时都要用它来找到父节点。我见过很多人在树状数组代码里死记x x (-x)和x - x (-x)一旦问起为什么是这个式子就说不清楚。其实搞懂了补码和按位与的数学原理这两个式子自然就“长”在脑子里了。5. 刷题实战中的高频事故与公式速查5.1 五大翻车现场实录数学公式在实战中并不总是一步到位相反我见过太多人在“最后一步”翻车。这里整理几个我亲身经历过的典型事故你可以对照着避坑。事故一忘记对负数取模取模的结果在大多数编程语言里可能带符号。比如(-5) % 3在 C 里的结果是 -2不是 2。如果你拿着这个负数直接去当数组下标或者计数得到的答案一定是错的。解决方式是统一加模数再取模((x % MOD) MOD) % MOD。这个习惯我养成之后再也没在负数取模上吃过亏。事故二除法取模直接做除法前面说过模意义下不能直接做除法。有一次我写组合数公式偷懒直接在表达式里写成C(2n, n) / (n1)结果对小数据全部正确一上大数据就开始乱飘。排查半天才发现是忘记求逆元。从那以后我在代码里看到“斜杠”就会条件反射地警觉。事故三浮点数比较用等号算几何类题目时有时候需要判断两个浮点数是否相等。如果直接用double a double b多半会在精度上翻车。正确做法是加一个误差范围fabs(a - b) 1e-9。这个教训来自一次面积计算题因为直接比较导致判题系统一直报错。事故四预处理数组没开 long long前缀和、差分数组在 n 很大时中间值可能超过 int 范围。我在一道二维矩阵题里因为偷懒用int存前缀和结果一上大规模数据就溢出答案全部变成负数。后来所有涉及累加的预处理数组一律用long long这个习惯帮我避开了一大批隐蔽 bug。事故五递推式的初始条件写错卡特兰数、错排公式、斐波那契这些递推关系边界条件一旦写错整个数列就全都偏了。我常用的自查办法是先手动算前几项比如 n0、1、2、3和题目样例或已知结论做对比确认无误后再放心递推。这个“小数据验证”的习惯值得刻在脑子里。我把这些事故整理成了速查表问题常见表现解决思路负数取模答案莫名比预期小((x % MOD) MOD) % MOD除法取模大数据错误、小数据正确用费马小定理或扩展欧几里得求逆元浮点比较用比较误差大用fabs(a-b) eps判断数据溢出答案变成负数预处理数组用long long边界条件错误小数据就不对先手算几个小项验证5.2 建立公式直觉的三个日常习惯公式不是考前突击就能掌握的它需要在日常刷题中不断积累。我总结了三个对我特别有用的习惯你可以直接拿去用。第一个习惯拿到题先看数据范围再动手。如果题目给的 n 是 10^5 甚至 10^9说明它大概率不是让你暴力枚举的。这时候我会停下来想一想这个规模下有哪些数学工具能用是前缀和是矩阵快速幂还是容斥原理数据范围本身就在暗示你该用哪个公式。第二个习惯把公式当成“解题关键词”来复盘。每次做完一道题我会在笔记里写清楚“这道题用到哪个公式、为什么这个公式能切入、还有哪些题属于同一类模型”。这样做的好处是当你之后再遇到类似的题目时大脑会不由自主地跳出那个公式。我从“看到数对括号想枚举”到“看到数对括号直接想到卡特兰数”就是靠这个复盘习惯实现的。第三个习惯别光看题解亲手推导一遍。就算只是三行的推导也要在草稿纸上写出来。因为看题解是“别人告诉你结果”手推才是“自己验证因果”。我在理解二维前缀和公式时一开始也是懵的但当我画了一个 3×3 的矩阵把每个区域都标出来之后那个容斥公式就再也不会记混了。5.3 公式速查小抄最后送上一份精简版速查小抄建议收藏备用。它不能替代理解但能在你卡壳的时候给你一个支点。公式表达式使用提醒一维前缀和pre[i] pre[i-1] a[i]区间和 pre[r] - pre[l-1]二维前缀和S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]注意左上角被减两次等比数列求和S_n a*(1-q^n)/(1-q)取模时用逆元处理分母卡特兰数h(n) C(2n, n)/(n1)n 大时记得求逆元组合数(O(1)查询)C(n, k) fact[n]*inv_fact[k]*inv_fact[n-k]需要预计算阶乘和逆元几何分布期望E 1/p适用于首次成功实验容斥原理加单集合减两两交集加三三交集每一项系数是 (-1)^k错排公式D(n) (n-1)*(D(n-1)D(n-2))初始条件D(0)1, D(1)0最低位 1x (-x)树状数组、二进枚举常用2 的幂判定n (n-1) 0记得单独处理 n06. 我的一点私房心得公式是用来推导的不是用来背的写到这里我想再说一件比公式本身更重要的事。我在带新人时经常说一句话公式是理解问题的结果而不是解决问题的起点。如果你只是背下了卡特兰数的通项公式而不知道它的递推式来自“枚举第一个右括号的位置”那么题目稍微变形你就又会被卡住。我自己有个小方法每次遇到一个陌生公式先花十分钟亲手推一遍。哪怕推不出来只推一半也比完全不推强。因为推导过程会逼你去关注“这个公式为什么长这样”而不是把公式当成一个黑盒。很多看起来唬人的公式拆开之后都只是一层窗户纸。另外我强烈建议你在刷题时准备一个“公式触发清单”。比如“见到连续区间、子数组、和/差”——想前缀和、差分、哈希。“见到 n 巨大、递推关系”——想矩阵快速幂、特征方程。“见到括号序列、出入栈、二叉树计数”——想卡特兰数。“见到排列、子集、计数”——想容斥、组合数、错排。“见到概率、期望”——想几何分布、全期望。这个清单看起来简单但它能帮你在考场上快速建立“数学图示”而不是陷入盲目试代码的泥潭。我个人在实际操作中最深的体会是算法题的最高分水岭往往不在代码而在数学上的选择。同一个问题用不同的公式去描述复杂度可能是天差地别。所以与其疯狂刷题比你多写了多少行代码不如在每道题结束之后多问自己一句“这道题背后的数学公式是什么”你把这个习惯坚持下去会发现那些曾经让你头疼的公式慢慢都变成了解题时最顺手的武器。至少在“伍六七带你学算法”这条路上我能看到的最快的成长路径就是先搞定这群被忽视的数学公式。
