偏门/变态 Trick 秒杀清单
这份清单专门收录那些在算法竞赛中“见效极快、推导极难”的数学结论。遇到符合特征的题目,直接套公式即可。
一、 数论与代数“一击必杀”结论
1. 麦乐鸡定理 (买不到的数目 / Frobenius 币问题)
- 题目特征:给定两个互质的正整数 a 和 b,问用这两个数通过非负整数次相加,最大不能组合出的数是多少?或者问共有多少个数不能被组合出?
- 秒杀结论:
- 最大不能组合出的数:a×b−a−b
- 不能组合出的数的总个数:2(a−1)(b−1)
- 陷阱:必须保证 gcd(a,b)=1。如果 gcd(a,b)>1,则不能组合出的数有无限个。
2. 互质和定理
- 题目特征:求小于等于 N 且与 N 互质的所有数的和。
- 秒杀结论:Sum=2N×ϕ(N) (当 N>1 时)。ϕ(N) 是欧拉函数。
3. 威尔逊定理 (阶乘取模)
- 题目特征:题目出现大数的阶乘对某个数取模,且形如 (P−1)!(modP)。
- 秒杀结论:当且仅当 P 为质数时,(P−1)!≡−1(modP) (也就是 ≡P−1)。
- 衍生:如果问 (P−2)!(modP),结论是 1。
4. 勒让德定理 (阶乘质因子分解)
- 题目特征:问 N! (N 的阶乘)末尾有多少个零?或者问 N! 能被质数 p 的最高多少次幂整除?
- 秒杀结论:N! 中质因子 p 的个数为 ∑k=1∞⌊pkN⌋。求末尾零的个数,就是求质因子 5 的个数(因为 2 的个数显然远多于 5)。
5. 平方和定理 (费马二平方和定理)
- 题目特征:问一个整数能否表示为两个完全平方数之和 x2+y2。
- 秒杀结论:一个数可以表示为两平方和,当且仅当其质因数分解中,所有形如 4k+3 的质因子,其指数都为偶数。
- 衍生:所有形如 4k+1 的奇素数必定能唯一地写成两个平方数之和。
6. 平方差定理(两平方数之差)
- 题目特征:问一个整数 n 能否表示为两个完全平方数之差,即 x2−y2;或者要求快速构造这两个平方数。
- 秒杀结论:
- 因为 x2−y2=(x−y)(x+y)
- 一个正整数 n 可以表示为两个平方数之差,当且仅当 n≡2(mod4)
- 也就是说:
- 若 n 是奇数,一定可以表示
- 若 n 是 4 的倍数,一定可以表示
- 若 n≡2(mod4),一定不可以表示
- 快速构造:
- 若 n 为奇数:
n=(2n+1)2−(2n−1)2
- 若 n 为 4k:
n=(k+1)2−(k−1)2
- 陷阱:
- 若题目要求 x,y 为正整数,要额外检查构造出来的 y 是否大于等于 1
- n=0 时有 02−02=0
7. 三平方和定理(Legendre 三平方定理)
- 题目特征:问一个正整数能否表示为三个完全平方数之和。
- 秒杀结论:
- 一个正整数 n 能表示为三个平方数之和,当且仅当
n=4a(8b+7)
- 使用方法:
- 不断把 n 除以 4
- 若最后剩下的数模 8 等于 7,则不能表示
- 否则可以表示
- 衍生:
- 配合拉格朗日四平方和定理:任意正整数都能表示成至多四个平方数之和
8. 约数个数公式 / 约数和公式
- 题目特征:求一个数的约数个数、所有约数之和、或者满足某些整除条件的方案数。
- 前提:设
n=p1a1p2a2⋯pkak
- 秒杀结论:
- 约数个数:
d(n)=(a1+1)(a2+1)⋯(ak+1)
- 约数和:
σ(n)=i=1∏k(1+pi+pi2+⋯+piai)=i=1∏kpi−1piai+1−1
- 题目特征补充:
- “有多少种乘法拆分”
- “多少个因子满足某性质”
- “枚举约数但数据很大”
9. 线性同余方程(扩展欧几里得)
- 题目特征:求
ax≡b(modm)
是否有解,有多少解,或求最小正整数解。
- 秒杀结论:
- 设 d=gcd(a,m)
- 方程有解当且仅当 d∣b
- 若有解,先把式子同时除以 d:
dax≡db(moddm)
- 此时 da 与 dm 互质,可用扩展欧几里得求逆元
- 补充:
- 模逆元存在当且仅当 gcd(a,m)=1
- 若存在逆元,则
x≡a−1b(modm)
10. 中国剩余定理(CRT)
- 题目特征:求一个数同时满足多个同余条件:
x≡a1(modm1),x≡a2(modm2),…
- 秒杀结论:
- 若各模数两两互质,则解在模 M=∏mi 意义下唯一
- 可直接套 CRT 合并
- 实战思路:
- 先求总模数 M
- 对每个方程设 Mi=M/mi
- 求 Mi 在模 mi 下的逆元 ti
- 则
x≡∑aiMiti(modM)
- 陷阱:
- 若模数不互质,不能直接套标准 CRT,要判是否矛盾,再做扩展 CRT
二、 博弈论“玄学”模型
校赛最喜欢考博弈论结论题,除了 Nim,以下两个模型出场率极高且很难现场推导:
1. 威佐夫博弈 (Wythoff's Game) & 黄金分割比
- 题目特征:有两堆石子,每次有两种操作:要么在其中一堆取任意数量,要么在两堆中取相同数量。最后取完者胜。
- 秒杀结论:利用黄金分割率 ϕ=21+5。
假设当前两堆石子数为 (x,y) 且 x≤y,两堆的差值为 d=y−x。
如果 x==⌊d×ϕ⌋,则当前状态为必败态(先手必败)。否则先手必胜。
2. 斐波那契博弈 (Fibonacci Nim)
- 题目特征:只有一堆石子,共 N 个。先手第一次可以取任意多个,但不能全取完。之后每次每个人取的个数不能超过上个人取数的 2 倍。最后取完者胜。
- 秒杀结论:当且仅当 N 是斐波那契数时,先手必败。否则先手必胜。(基于 Zeckendorf 定理,任何正整数都能唯一表示为不相邻的斐波那契数之和)。
3. Nim 游戏 & 异或和定理
- 题目特征:有若干堆石子,每次从某一堆取任意正数个,最后取完者胜。
- 秒杀结论:
- 设所有堆大小异或和为
x=a1⊕a2⊕⋯⊕an
- 若 x=0,则当前是必败态
- 若 x=0,则当前是必胜态
- 经典操作:
- 必胜时,总能找到一堆,把它变成某个更小值,使得修改后总异或和为 0
4. SG 函数(Sprague-Grundy)
- 题目特征:复杂博弈拆成若干个独立子游戏,然后每步只操作其中一个子游戏。
- 秒杀结论:
- 每个状态有一个 SG 值
- 多个独立子游戏的总 SG 值为所有子游戏 SG 值的异或和
- 总异或和为 0 则必败,否则必胜
- 定义:
- 一个状态的 SG 值等于它所有后继状态 SG 值集合的 mex
- 题感提示:
- 看见“多个局面彼此独立”“每次只动一部分”,优先考虑 SG
三、 几何与离散图论 Trick
1. 皮克定理 (Pick's Theorem) - 格点多边形面积
- 题目特征:给定一个顶点全在整点(坐标全为整数)上的多边形,求其面积、或者求多边形内部/边界的整点个数。
- 秒杀结论:Area=I+2B−1。
其中 Area 为多边形面积(可用叉积算),I 为多边形内部的整点数,B 为多边形边界上的整点数。
技巧:线段 (x1,y1) 到 (x2,y2) 上的整点个数为 gcd(∣x1−x2∣,∣y1−y2∣)+1。边界整点总数 B 就是各条边上整点数相加减去顶点数。
2. 欧拉公式 (平面图)
- 题目特征:给出平面上若干点和不相交的线段(或求平面被划分成几块)。
- 秒杀结论:对于任何连通的平面图,满足 V−E+F=2。
(V 是顶点数,E 是边数,F 是面数,包含最外部的无限面)。求划分区域数就是求 F−1=E−V+1。
四、 经典整数数列 (遇事不决先打表)
在校赛中,如果你推出前 5 项,发现符合下面数列特征,直接套公式,不需要证明。
1. 卡特兰数 (Catalan Number)
- 前几项:1,1,2,5,14,42,132,429,1430…
- 题目特征:
- N 对括号的合法匹配方案数。
- N 个节点构成的不同二叉树数量。
- 凸 N+2 边形划分为三角形的方案数。
- 进出栈的合法序列数。
- 在 N×N 网格中,从 (0,0) 走到 (N,N) 且不越过对角线的路径数。
- 秒杀公式:Cn=n+1(n2n)=(n2n)−(n−12n)。
2. 错排数 (Derangement)
- 前几项:0,1,2,9,44,265,1854…
- 题目特征:N 个人抽 N 份礼物,每个人都抽不到自己准备的礼物的方案数;N 封信装错信封方案数。
- 秒杀公式:
- 递推:Dn=(n−1)×(Dn−1+Dn−2)。
- 通项近似:Dn=⌊en!+0.5⌋ (直接用阶乘除以自然常数 e 四舍五入)。
3. 贝尔数 (Bell Number)
- 前几项:1,1,2,5,15,52,203,877…
- 题目特征:把 N 个不同的元素划分成若干个(无序)非空集合的方案数。
- 秒杀公式:没有简单的闭式,通常用第二类斯特林数求和 Bn=∑k=0nS(n,k),或者使用贝尔三角形递推(类似杨辉三角,但 Ai,1=Ai−1,i−1,且 Ai,j=Ai−1,j−1+Ai,j−1)。
- S(n,k)=k!1∑i=0k(−1)i(ik)(k−i)n
4. 第二类斯特林数(Stirling Number of the Second Kind)
- 题目特征:把 n 个不同元素划分成恰好 k 个非空无序集合的方案数。
- 秒杀结论:
- 递推:
S(n,k)=S(n−1,k−1)+k⋅S(n−1,k)
- 题感:
- 最后一个元素单独成一组
- 或加入已有的 k 组之一
- 和贝尔数关系:
Bn=k=0∑nS(n,k)
五、 期望与概率微操
1. 邮票收集问题 (Coupon Collector's Problem)
- 题目特征:有 N 种不同的卡片,每次买盲盒等概率获得其中一张,求收集齐所有 N 种卡片期望购买的次数。
- 秒杀结论:E=N×∑i=1Ni1。大约等于 NlnN+γN。
2. 随机游走期望
- 题目特征:一条直线上有 0…N 个点。在位置 i 时,有 p 的概率走到 i+1,有 1−p 的概率走到 i−1。求从 A 走到 B 的期望步数。
- 秒杀结论:这通常是个一阶差分常系数线性递推方程。如果 p=0.5,从 0 走到 N 的某一边界,期望经常是二次方级别的(例如从原点到距离 D 的边界,期望步数是 D2)。建议直接设未知数 Ei 然后解三对角矩阵(或者找规律)。
3. 容斥原理(至少一个 / 一个都没有)
- 题目特征:计数中出现“至少一个满足”“一个都不满足”“恰好若干个满足”。
- 秒杀结论:
- 至少一个满足
∣∪Ai∣=∑∣Ai∣−∑∣Ai∩Aj∣+∑∣Ai∩Aj∩Ak∣−⋯
- 经典模型:
- 错排
- 若干条件至少满足一个
- 覆盖 / 禁止位置 / 染色限制
- 技巧:
六、 组合恒等式秒杀
1. 前缀组合数求和
- 题目特征:出现
k=0∑n(mk)
或相近形式。
- 秒杀结论:
k=m∑n(mk)=(m+1n+1)
- 题感:
2. 范德蒙德卷积
- 题目特征:出现双组合乘积求和:
k∑(kn)(r−km)
- 秒杀结论:
k∑(kn)(r−km)=(rn+m)
- 题感:
- “从两组物品里总共选 r 个”的计数,既可分类讨论,也可一步直选
七、 图论 / 结论型 Trick(补充)
1. 握手定理
- 题目特征:无向图中点的度数、奇度点个数、边数之间关系。
- 秒杀结论:
- 所有点度数和等于边数的两倍:
∑deg(v)=2E
- 奇度点个数一定是偶数
- 常见用途:
2. 欧拉路 / 欧拉回路判定
- 题目特征:要求一笔画、每条边恰好经过一次。
- 秒杀结论(无向图):
- 存在欧拉回路:所有非零度点连通,且所有点度数为偶数
- 存在欧拉路但非回路:所有非零度点连通,且恰有两个奇度点
- 题感: