算法竞赛数学套路
这章按“题面长什么样 → 把什么量写出来 → 怎样算”组织。每个模式都给出可手算的小例、成立条件与实现入口。引用的原题用来提供练习模型;没有题解的原题链接,不代表其中已经给出了本章推导。
实现接口见 算法竞赛模板增补,代数结构与相应代码见 抽象代数的竞赛用法。本章的 cp:: 接口来自配套 ready/cp_ready.hpp,索引约定以接口说明为准。
0. 题面信号 → 第一反应
| 题面信号 | 先定义的量 | 应用方向 |
|---|---|---|
| 若干数一起平移、要求最终同余 | 差值及差值的 GCD | 1、2、27 |
| 乘积、完全幂、约数、阶乘整除 | 每个质数的指数 | 3、26 |
| GCD 恰好是某值、两数互质 | “都被 d 整除”的宽条件 | 4 |
| 区间和整除、数量相等或比较 | 前缀余数、前缀差 | 25、23 |
| 非空、至少一个、每类都出现 | 坏事件及其交集 | 5、6、29 |
| 不能越界的括号、网格路径 | 前缀高度、第一次越界点 | 30 |
| 旋转相同、重复执行置换 | 置换循环及固定点 | 20、35 |
| 配对指标相加、二项式加权 | 系数序列或生成函数 | 12 |
| XOR 可达、开关翻转、解的个数 | GF(2) 的秩与自由变量 | 31 |
| 巨大步数、固定规则迭代 | 状态转移、特征递推 | 28、34 |
| 树的数量、保证联通的选边方案 | 拉普拉斯矩阵 | 32 |
| 最大值、第 k 小、等到收集齐 | CDF、指示变量、等待阶段 | 15–17、36、37 |
| 最小绝对偏差、重排、平均分配 | 斜率、交换差、边际费用 | 18、19、38、39 |
| 操作很多但每步变化受限 | 守恒量、势能、相邻差 | 40、41 |
一、数论:把数值限制改写成整除与指数
1. 同步操作:先研究差值
识别:几个数同时加减;操作似乎要追踪大数,但它们的相对差异很小。
转化与应用:若 ,则 不变。要使平移后两数都被 整除,必要且充分的是 且 。先分解 ,再枚举允许的约数或质因子;若随后同时除以 ,新差值为 ,状态可改为 。
小例: 的差是 6。同时减 2 后变成 ,可同除 6;要同除 5 则无论怎样同步平移都不可能,因为 。
前提与代价:题目必须允许相应平移,并核对正数范围、方向和费用。 时不能靠枚举其质因子解决。试除分解 ;不是对所有“同时操作”题都存在同样递推。
2. 自选模数:同余变整除
识别:自己选模数,让一组数余数相同;询问最大可行模数或有多少模数。
转化与应用:写出 ,即 。求
所有候选恰为 的正约数,再检查题目额外限制;若求无上界的最大模数且 ,答案就是 。
小例: 的差值 GCD 为 6,可选 ;模 6 均余 2。
前提与代价: 代表原数全相同,可能没有有限最大值。指定余数 时还须 ,并改算 。求 GCD 为 ;列约数可 。其基础是扩展欧几里得维护的整数线性组合关系,参见 KACTL euclid 作者实现。
3. 乘积条件 → 质因子指数状态
识别:乘积为平方、完全 次幂;把一个给定整数拆成有序因子的方案数。
转化与应用:正整数 。完全 次幂要求所有指数和模 为 0;用前缀指数向量 ,区间条件成为 。平方时向量加法就是 XOR,同类前缀有 个便贡献 。
小例: 的非空平方乘积区间有 、、整个数组,共 3 个。若求 的正整数有序解,;分配两个指数分别有 、 种,乘积为 18。后一类模型见 ABC110 D 官方题解。
前提与代价:必须存规范指数向量,不能把质数的数值直接 XOR 当作无碰撞编码。 时仍比较两个前缀相等;若做“当前向量与另一个数配成完全幂”的查询,才查相反向量。0 与负号分别处理。筛最小质因子 ,分解每个数 ,向量比较/哈希费用另计。
4. GCD 恰好值:先算倍数条件,再反演
识别:统计 GCD 等于 的对、元组,或把所有 GCD 加起来;直接枚举每一对太慢。
转化与应用:令 为能被 整除的元素数, 为 GCD 恰为 的无序下标对数。宽条件包含所有倍数:
从大到小消去真倍数即可。若是长度 、每项在 的序列,把 换成 ;这是 ABC162 E 原题 的可行入口。
小例: 中 ,所以 ;GCD 之和为 4。
前提与代价:正整数、值域 可开数组时,倍数筛 ;接口 cp::exact_gcd_pairs。只要互质对可用 ;求 GCD 和可用 ,依据 ,见 KACTL phi 恒等式。有序、自配对和含 0 的模型需重新计数。
11. 模运算里的除法
识别:组合数、平均值、等价类计数中的除法;写出闭式后分母可能与模数不互质。
转化与应用:把“整数先除后取模”和“模数域内求逆”分开。后者只在 时可写 。一般模数用扩展欧几里得;接口 cp::inv_mod 返回可选值。其前提见 ACL inv_mod 文档。
小例:,但模 6 时 2 没有逆元,不能做 6*inv(2)。若已知整数 被正整数 整除,可算 ,再用 ;这里取模是非负余数,,除 2 得 3。
前提与代价:素数模阶乘组合数 cp::Comb<P> 要求预处理上界 。 可考虑 Lucas 的逐位组合数,但小组合数仍要可算。扩欧求逆 ,组合数预处理 、查询 。模 方法须证明整除并控制乘积范围。
13. 模素数的乘法 → 指数加法
识别:统计模 乘积的分布,反复合并乘积; 是素数且非零值域可以遍历。
转化与应用:找原根 ,建表 。非零乘法满足 ,于是将频数映射到指数域,做长度 的循环卷积;可先线性卷积再折叠下标。原根与有限循环群的前提见 抽象代数的竞赛用法。
小例:模 7 取原根 3,幂依次是 。 的指数为 ,对应结果 1。
前提与代价:0 单独统计;单位元 1 的指数是 0。合数的全部非零剩余不一定构成循环群,不可照搬。已知原根后建表 ,每次卷积 ;cp::convolution 的系数模数与这里的剩余模数 是两个不同角色。普通卷积限制见 ACL convolution。
14. 除法:整除分块与 floor_sum 分清
识别: 可到 ,公式含 ;或者要数一条直线下面的格点。
转化与应用:前者从 出发,令 ,区间 商相同,用前缀权重一次求贡献。比如
正是 CSES Sum of Divisors 的原题模型。后者 则用类欧几里得 cp::floor_sum_nonnegative。
小例: 时加权分块为 。另有 。
前提与代价:商分块 ;线性分子 floor_sum 为 。配套接口要求非负参数、、答案可放进 i128;与 ACL 的溢出约定不同。负数用 cp::floor_div/ceil_div,C++ 向零截断不等于数学 floor。
25. 区间整除与抽屉:把连续段变成两个前缀
识别:存在/统计区间和被 整除;长度与模数接近,要求证明一定有解。
转化与应用:令 ,区间和整除等价于两个前缀余数相同。扫描时先加 cnt[P_i] 再递增;存在性方面, 个前缀放进 个余数类,必有两个相同。CSES Subarray Divisibility 提供了含负数的练习模型。
小例: 模 3 的前缀是 ,余数 0 出现 3 次,答案 。
前提与代价:;负数余数规范为 。求余数 的区间应在线查询 ,不能只把频数任意两两配对而忽略顺序。数组 或哈希期望 ;存在性只保证非空区间,不保证题目额外长度限制。
26. 阶乘和组合数的整除:数质因子,不构造大整数
识别: 末尾有几个 0、组合数能否被 整除、约分后剩多少个 。
转化与应用:每个 的倍数贡献一次、 的倍数再贡献一次,因此
v_p\binom nr=v_p(n!)-v_p(r!)-v_p((n-r)!).$$ 循环不断做 `n/=p; ans+=n`,避免直接生成 $p^t$ 溢出。十进制尾零取 $\min(v_2,v_5)$;一般基数 $B=\prod p^{b_p}$ 取 $\min_p\lfloor v_p/b_p\rfloor$。 **小例**:$v_5(25!)=5+1=6$,所以 $25!$ 十进制尾零为 6。$\binom52=10$ 的 $v_2=3-1-1=1$。 **前提与代价**:$p$ 必须是质数;合数基数先分解。每个质数 $O(\log_p n)$。若还要组合数模 $p^k$,须同时维护去掉 $p$ 因子的单位部分,不能只靠指数;可接 [抽象代数的竞赛用法](/posts/obsidian/%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B0%E7%9A%84%E7%AB%9E%E8%B5%9B%E7%94%A8%E6%B3%95/) 的“单位与可逆元”判断。质因子指数分配的原题对应见 [ABC110 D 官方题解](https://img.atcoder.jp/abc110/editorial.pdf)。 ### 27. 周期条件同时满足:广义 CRT 与同余方程 **识别**:多个定期事件同时发生;某量对几个模数的余数分别已知;模数未必互质。 **转化与应用**:合并 $x\equiv r\pmod m$ 与 $x\equiv s\pmod n$,代入 $x=r+mt$,得到 $mt\equiv s-r\pmod n$。设 $g=\gcd(m,n)$,无解当且仅当 $g\nmid(s-r)$;否则除以 $g$ 后求逆,得到唯一模 $\operatorname{lcm}(m,n)$ 的解类。 **小例**:$x\equiv2\pmod6,x\equiv5\pmod9$:$6t\equiv3\pmod9$,约成 $2t\equiv1\pmod3$,故 $t\equiv2$,$x\equiv14\pmod{18}$。 **前提与代价**:周期为正数,余数先规范化;“没有解”与“最早解为 0”不同。合并 $k$ 条约束约 $O(k\log L)$,$L$ 是合并后的模数规模。板子 `crt.cpp` 处理一般正模数,LCM 超过 i64 会报溢出;接口语义可对照 [ACL crt](https://atcoder.github.io/ac-library/production/document_en/math.html)。 ### 28. 幂塔和重复乘法:周期从哪里开始? **识别**:指数极大、十进制字符串指数、重复乘同一个数;想把指数直接对 $\varphi(M)$ 取模。 **转化与应用**:先判断 $\gcd(a,M)$。互质时欧拉定理允许周期化;非互质时,序列可能先进入前导段,之后才循环。也可将 $M$ 分解成互质质数幂,对 $v_p(a)$ 分析何时幂变成 0,再 CRT 合并。 **小例**:模 8 的 $2^e$ 在 $e=1,2,3,4$ 时为 $2,4,0,0$;直接把 $e=4$ 取成 $e\bmod\varphi(8)=0$,会误得 1。相反,模 7 的 $3^{100}$ 可用 $100\bmod6=4$,结果 4。 **前提与代价**:欧拉降幂要求互质;非互质要同时知道指数余数与是否超过阈值,板子 `extended_euler.cpp` 处理十进制大指数。0 指数和题目对 $0^0$ 的约定独立检查。[CSES Exponentiation II](https://cses.fi/problemset/task/1712) 明确给出了这类边界。读长为 $D$ 的指数加快速幂通常 $O(D+\log M)$,分解 $M$ 费用另计。 ## 二、计数:先确定对象、交集和唯一归属 ### 5. 集合关系:SOS 方向与容斥 **识别**:bit 集合包含、两个数 AND 为 0、选择若干数后 AND/OR 的取值。 **转化与应用**:子集和 $F(S)=\sum_{T\subseteq S}f(T)$ 从少 bit 向多 bit 传播;超集和反向。`x & y == 0` 等价于 $y\subseteq FULL\mathbin{\char94}x$。若数非空下标子集 AND 为 0,令 $c_S$ 为包含 $S$ 所有 bit 的元素数,则 $$\#=\sum_{S\subseteq FULL}(-1)^{|S|}(2^{c_S}-1).$$ 固定某个选择、其 AND 为 $A$,上式把它计算 $\sum_{S\subseteq A}(-1)^{|S|}=[A=\varnothing]$ 次。 **小例**:$[1,2,3]$ 中 AND 为 0 的非空下标子集只有 $\{1,2\}$ 与 $\{1,2,3\}$,共 2 个。 **前提与代价**:固定 $B$ 位、$a_i\in[0,2^B)$;相同数值的不同下标仍是不同选择。`cp::sos`、`subset_witness`、`count_and_zero`,$O(n+B2^B)$。位外层才能保证每种选位组合传播一次;整数 SOS 要防溢出。三种位卷积的原作者接口见 [KACTL FastSubsetTransform](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/numerical/FastSubsetTransform.h)。 ### 6. 严格多数:坏事件可能互斥 **识别**:要求没有一种颜色/类型占所选总数的一半以上;直接做多类别计数状态太大。 **转化与应用**:若每个选中对象只属一类,两个类别不可能同时占严格多数。因此合法数等于总数减去每个“类别 $j$ 占严格多数”的方案数。固定 $j$,只需跟踪差 $d=\#j-\#其他$,把多类变成两类。 若每行可不选或选一个对象,权重为 $a_{ij}$、行和 $s_i$,则总非空方案 $\prod_i(1+s_i)-1$,转移 $$new[d]=old[d]+a_{ij}old[d-1]+(s_i-a_{ij})old[d+1].$$ **小例**:三次独立选 A/B,总数 8。A 严格多数有 4 种,B 有 4 种,所以无严格多数的方案为 0;两次选择则合法的是 AB、BA,共 2 种。 **前提与代价**:“至少一半”不是互斥事件;对象可同时属于多类也不适用。$n$ 行、$m$ 类,直接差值 DP 为 $O(mn^2)$、空间 $O(n)$。先写出两个坏事件不可能同时发生的证明,再决定不做高阶容斥。 ### 8. 贡献法:先换求和顺序 **识别**:所有区间/点对的和;每个对象在许多答案里重复出现。 **转化与应用**:把“枚举所有答案再求和”交换成“枚举一个元素/边,数它被用几次”。1-based 数组元素 $a_i$ 对所有子数组元素和贡献 $a_i i(n-i+1)$;树边权 $w$,删边一侧有 $s$ 点,对无序点对距离和贡献 $ws(n-s)$。 **小例**:数组 $[1,2,3]$ 贡献 $1\cdot3+2\cdot4+3\cdot3=20$。三点路径边权 2、3,贡献 $2\cdot1\cdot2+3\cdot2\cdot1=10$。 **扩展与前提**:子数组最大值可令左边最近严格大于为 $L$、右边最近大于等于为 $R$,贡献 $a_i(i-L)(R-i)$;相等元素左右必须一边严格、一边非严格,指定唯一归属。$[2,2]$ 的三个子数组最大值之和是 6。树 DFS/单调栈均为 $O(n)$,乘法在运算前转 i128。贡献求和的概率版本见 36。 ### 9. 分球入盒、上下界与组合恒等式 **识别**:相同物品分给有编号的容器;整数解之和固定,每项带上下界。 **转化与应用**:$x_1+\cdots+x_k=n,x_i\ge0$,用 $k-1$ 个隔板分出 $k$ 组,数量 $\binom{n+k-1}{k-1}$;[CSES Distributing Apples](https://cses.fi/problemset/task/1716) 正是此模型。有下界先令 $y_i=x_i-L_i$;上界 $y_i\le V_i$ 用容斥: $$\sum_{S\subseteq[k]}(-1)^{|S|}\binom{n-\sum_iL_i-\sum_{i\in S}(V_i+1)+k-1}{k-1}.$$ **小例**:$x_1+x_2+x_3=4,0\le x_i\le2$,总数 $\binom62-3\binom32=15-9=6$。 **前提与代价**:容器有编号、物品不可区分;若物品可区分,通常变成多项式系数或 $k^n$。无效上标的组合数视为 0;$k=0$ 单独处理。一般上界容斥 $O(2^k)$,相同上界可按 $|S|$ 合并成 $O(k)$。乘积求和先尝试按选择数分类的范德蒙德恒等式 $\sum_i\binom ai\binom b{r-i}=\binom{a+b}r$。 ### 10. 组合题:先固定“哪些位置”,再数“填什么值” **识别**:先选位置再分颜色/对象;“出现某种结构”的见证可能不唯一;公式看似是几个组合数相乘。 **转化与应用**:把方案显式写为元组,例如“选出的行集合 $R$、公共颜色 $c$、列集合 $C$”。验证每个最终对象对应几个元组,才能决定相乘后是否除重。多重集排列可依次选每种字符的位置,得到 $n!/\prod_c n_c!$;作者实现见 [KACTL multinomial](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/combinatorial/multinomial.h)。 **小例**:AAB 的不同排列为 $\binom32\binom11=3$。但“统计有相等字母对的长度 3 二元串”不能直接选一对位置再选公共颜色再填另一个:这会得到 $3\cdot2\cdot2=12$,AAA/BBB 各被算 3 次,真实所有 8 个串都满足。 **前提与代价**:鸽巢证明需明确“鸽子是什么、巢是什么、每只鸽子是否唯一入巢”。见证不唯一时规定唯一归属、容斥或双计数,不能随意除一个常数。阶乘预处理 $O(n)$ 后多项式系数通常 $O(\#类别)$;分母逆元仍受 11 的限制。 ### 20. 对称计数:Burnside 的适用边界 **识别**:旋转/翻转后视为同一方案;直接除以对称操作个数会得到非整数或不对的答案。 **转化与应用**:先确定作用群 $G$,再逐个操作数保持不变的对象: $$\#\text{等价类}=\frac1{|G|}\sum_{g\in G}|\operatorname{Fix}(g)|.$$ 颜色必须在操作产生的每个位置循环上相同;有 $c$ 个循环、每处任取 $q$ 色时固定点数 $q^c$。该方法见 [Competitive Programmer's Handbook 第 22 章](https://cses.fi/book/book.pdf)。 **小例**:$2\times2$ 黑白格仅按旋转去重,四种旋转的循环数为 $4,1,2,1$,答案 $(16+2+4+2)/4=6$;原题应用见 [CSES Counting Grids](https://cses.fi/problemset/task/2210)。长度 4 的二色项链仅旋转去重,同样得到 6。 **前提与代价**:合法集合必须在群作用下封闭;固定某个编号位置的限制可能破坏对称。旋转与二面体群(含镜像)分开。直接枚举操作与循环 $O(|G|n)$,规则旋转常能按 GCD/约数合并。模数整除 $|G|$ 时不能直接求逆,回看 11。 ### 29. 至少一个、每类都出现、没人拿回原物:显式定义坏事件 **识别**:至少被一个数整除;分配后每类都出现;排列无固定点。 **转化与应用**:令 $A_i$ 为第 $i$ 个坏事件,再计算交集而不是凭印象写正负号。$k$ 个有编号盒子都非空,放 $n$ 个有区别的球: $$\sum_{j=0}^k(-1)^j\binom kj(k-j)^n.$$ 至少被一个给定数整除则交集是被其 LCM 整除,贡献 $\lfloor N/\operatorname{lcm}\rfloor$;只有两两互质时才能把 LCM 简化为乘积。[CSES Prime Multiples](https://cses.fi/problemset/task/2185) 给定的是不同质数。 **小例**:$1\ldots20$ 中被 2 或 5 整除有 $10+4-2=12$ 个。3 个有编号球放入 2 个非空盒子有 $2^3-2=6$ 种。 **前提与代价**:直接子集容斥 $O(2^k k)$,构造 LCM 前先检查是否超过 $N$,避免溢出。错排数由相同思路得 $D_n=\sum_j(-1)^j\binom nj(n-j)!$,也可 $D_n=(n-1)(D_{n-1}+D_{n-2})$、$D_0=1,D_1=0$;$D_4=9$,可练 [CSES Christmas Party](https://cses.fi/problemset/task/1717)。 ### 30. 前缀不能为负:Catalan 与反射 **识别**:合法括号、上右路径不能越过对角线;总数容易,难点是每个前缀都合法。 **转化与应用**:把左括号记 $+1$、右括号记 $-1$。从高度 0 走 $2n$ 步回 0,总数 $\binom{2n}n$;把第一次到 $-1$ 之前的步反向,坏路径与终点高度 2 的路径一一对应,数为 $\binom{2n}{n-1}$。两者相减得到 Catalan 数。 若给定前缀始终合法、当前高度 $h$、余 $m$ 步,则还需 $u=(m-h)/2$ 个上步,完成数为 $$\binom mu-\binom m{u+h+1}.$$ **小例**:长度 6、前缀 `(()`,$h=1,m=3,u=1$,完成数 $\binom31-\binom33=2$,与 [CSES Bracket Sequences II](https://cses.fi/problemset/task/2187) 的样例相符。 **前提与代价**:先检查总长奇偶、前缀是否曾负、$u$ 是否为整数且在 $[0,m]$;有多种括号或额外禁区需重新建模。组合数预处理 $O(N)$ 后每问 $O(1)$;用相减形式可避开对 $n+1$ 的模除法。 ## 三、代数:把可达、计数和巨大步数变成结构运算 ### 12. 卷积:先判断指标如何组合 **识别**:要对所有 $k$ 计算 $\sum_i a_i b_{k-i}$,或合并两组和、长度、选择数量的分布。 **转化与应用**:写 $A(x)=\sum_i a_ix^i$,乘法中 $x^ix^j=x^{i+j}$,所以 $[x^k]AB$ 就是指标和为 $k$ 的配对数。若权重为 $\sum_i\binom ni a_ib_{n-i}$,先除阶乘:卷积 $A_i=a_i/i!,B_i=b_i/i!$,再乘 $n!$。 **小例**:$[1,2]*[3,4]=[3,10,8]$。标记对象分成两部分时,$a_i=b_i=1,n=3$ 得 $\sum_i\binom3i=8$,对应 $3!\sum_i1/(i!(3-i)!)$。 **前提与代价**:指标取模是循环卷积,按 OR/AND/XOR 合并是相应集合变换,$ij=k$ 则是约数卷积;不能把这些直接当普通 NTT。`cp::convolution` 固定模 $998244353$,二次幂长度至多 $2^{23}$,$O(N\log N)$;限制见 [ACL 文档](https://atcoder.github.io/ac-library/production/document_en/convolution.html)。阶乘归一化须分母可逆。多模 CRT 还原后再取任意模,必须有真实系数范围保证或拆系数,不能只看目标模数互质。 ### 31. XOR 可达与开关系统:先求秩,再数方案 **识别**:每个操作最多用一次且只翻转 0/1;选若干数 XOR 成目标;问多少种选择可达同一结果。 **转化与应用**:把每次操作写成一列 0/1 向量,是否选择操作记为 $x_i$,要求 $Ax=b$,运算在 GF(2)。消元若产生 $0=1$ 则无解;有解且 $n$ 个变量、秩 $r$,自由变量可任取,所以有 $2^{n-r}$ 组解。所有可达结果共有 $2^r$ 个。 **小例**:可选数 $[1,2,3]$ 的向量秩为 2,因为 $1\oplus2=3$。8 种下标选择映到 4 种结果,每个结果恰有 2 种原像;XOR 为 0 的是空集与三个全选。 **前提与代价**:这里的加法是 XOR,不是 OR;若要求恰选 $k$ 个,线性方程的解数不能直接套用。单数 $B$ 位的增量线性基 $O(nB)$;一般 $m\times n$ 系统朴素 $O(mn\min(m,n))$,bitset 可并行异或。秩/无解返回语义见 [KACTL SolveLinearBinary](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/numerical/SolveLinearBinary.h),实现见 [抽象代数的竞赛用法](/posts/obsidian/%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B0%E7%9A%84%E7%AB%9E%E8%B5%9B%E7%94%A8%E6%B3%95/)。 ### 32. 连通选边方案:Matrix-Tree 把树数变成行列式 **识别**:在给定无向图里选 $n-1$ 条边保持连通;数生成树或其权值乘积之和,边数无法子集枚举。 **转化与应用**:构造拉普拉斯矩阵 $L$:一条权为 $w$ 的非自环边 $(u,v)$,给 $L_{uu},L_{vv}$ 加 $w$,给 $L_{uv},L_{vu}$ 减 $w$。删去同一个顶点的行列后求行列式。结果等于每棵生成树中边权乘积的总和;全为 1 时就是树数。定理与多重边实例见 [MIT 18.212 Lecture 19](https://math.mit.edu/~apost/courses/18.212_2021/lectures/18212_lecture19.pdf)。 **小例**:三角形的约化矩阵为 $\begin{pmatrix}2&-1\\-1&2\end{pmatrix}$,行列式 $4-1=3$,对应删去三条边中的任一条。 **前提与代价**:无向图、允许平行边并累加,自环无贡献;不连通时行列式为 0。模素数可消元 $O(n^3)$、空间 $O(n^2)$,换行要变号,零主元必须找行交换。合数模不能对所有非零主元求逆。带方向的树有朝向约定,不能直接套这份无向构造;代码入口见 [抽象代数的竞赛用法](/posts/obsidian/%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B0%E7%9A%84%E7%AB%9E%E8%B5%9B%E7%94%A8%E6%B3%95/)。 ### 33. 大范围求和但答案低次:插值与有限差分 **识别**:求 $1^k+\cdots+N^k$,$k$ 小而 $N$ 极大;答案随参数像一个固定次数多项式。 **转化与应用**:先证明次数上界。因为离散差分 $F(N)-F(N-1)=N^k$,$F$ 在有理数上次数至多 $k+1$;求出 $F(0),\ldots,F(k+1)$ 后插值。等距点可用拉格朗日式 $$F(t)=\sum_{i=0}^d y_i\prod_{j\ne i}\frac{t-j}{i-j}.$$ 一般点插值的作者实现与 $O(d^2)$ 基线见 [KACTL PolyInterpolate](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/numerical/PolyInterpolate.h);该文件用浮点,模数题应另用域上的运算。 **小例**:平方和前四项 $F(0..3)=[0,1,5,14]$;一阶差 $1,4,9$,二阶差 $3,5$,三阶差 2。延伸下一项得二阶差 7、一阶差 16,$F(4)=30$。 **前提与代价**:有限数据“看起来多项式”不是证明;取模后采样点必须互异且分母可逆。素数模数 $P$ 下使用本方法求幂和,常规安全条件是 $k+1<P$。等距节点配前后缀积可 $O(d)$ 求一次值,预处理样本费用另计;已有样本点应直接返回其值。 ### 34. 固定规则重复巨大次:矩阵、递推与幺半群快速幂 **识别**:步数 $10^{18}$,每一步的线性转移相同;线性递推第 $N$ 项;等比和不能安全做除法。 **转化与应用**:把状态写成列向量 $v_{t+1}=Tv_t$,答案是 $T^Nv_0$。若是 $s_{t+1}=As_t+1$,增添常数 1 维,转移为 $\begin{pmatrix}A&1\\0&1\end{pmatrix}$;[ABC293 E 官方题解](https://atcoder.jp/contests/abc293/editorial/5955?lang=ja) 给出了这个应用。 也可直接维护 $(P_n,S_n)=(A^n,\sum_{i<n}A^i)$,连接长度 $a,b$ 的块:$(P_aP_b,S_a+P_aS_b)$。此结合运算可快速幂,不需要 $A-1$ 可逆。 **小例**:$A=3,N=4,M=7$,$S_4=1+3+9+27\equiv5$。Fibonacci 初值 $0,1$、递推系数 $1,1$,$F_{10}=55$。 **前提与代价**:转移若依赖时刻,需先合成周期或增广状态。$d$ 维普通矩阵为 $O(d^3\log N)$;已知 $d$ 阶递推可按特征多项式约化到 $O(d^2\log N)$,见 [KACTL LinearRecurrence](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/numerical/LinearRecurrence.h)。BM 需要域且已知递推阶数上界,足够多前缀才能保证恢复;有限项拟合不能替代后续递推存在性的证明,见 [作者 BM 接口](https://raw.githubusercontent.com/kth-competitive-programming/kactl/main/content/numerical/BerlekampMassey.h)。 ### 35. 置换反复执行:循环决定周期与交换次数 **识别**:一次操作是位置重排且可逆;问执行 $k$ 次后的结果、最少交换数或恢复原样的最早时间。 **转化与应用**:把置换拆成互不相交的有向循环。长度 $\ell$ 的循环上,执行 $k$ 次等于前进 $k\bmod\ell$;所有位置一起恢复的周期是各循环长度的 LCM。长度 $\ell$ 的循环用任意两点交换拆成单点最少需 $\ell-1$ 次,故总计 $n-c$ 次,$c$ 为循环数。 **小例**:置换由 $(1\ 2\ 3)(4\ 5)$ 构成,周期 $\operatorname{lcm}(3,2)=6$,任意交换复原最少 $(3-1)+(2-1)=3$ 次;执行 4 次后,前三点前进 1 格、后两点不变。 **前提与代价**:必须是双射;一般函数图还有入环树与前导段。相邻交换的最少次数是逆序对,不能用 $n-c$。拆环 $O(n)$;LCM 可能溢出,需按题意用大整数或质因子最大指数。用循环数统计对称固定点的进一步应用见 20;结构背景见 [抽象代数的竞赛用法](/posts/obsidian/%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B0%E7%9A%84%E7%AB%9E%E8%B5%9B%E7%94%A8%E6%B3%95/)。 ## 四、概率期望:拆事件、拆贡献、拆等待阶段 ### 15. 精确最大值概率:CDF 做差 **识别**:很多独立随机数的最大值/最小值;“恰好等于 $k$”不好计,所有值都不超过 $k$ 容易计。 **转化与应用**:独立均匀 $X_i\in\{1,\ldots,m\}$,$Y=\max X_i$,则 $$P(Y\le k)=(k/m)^n,\quad P(Y=k)=(k/m)^n-((k-1)/m)^n.$$ 再用 $E[Y]=\sum_k kP(Y=k)$,或尾和 $E[Y]=\sum_{k=1}^m[1-((k-1)/m)^n]$。独立但不同分布时把幂改成各 CDF 乘积。[CSES Candy Lottery](https://cses.fi/problemset/task/1727) 可直接练习。 **小例**:$n=2,m=3$,最大值的概率是 $1/9,3/9,5/9$,期望 $(1+6+15)/9=22/9$。 **前提与代价**:精确最大值不是“指定某一个位置等于 $k$、其余不超过 $k$”,后者会因并列最大重复计数。$n\ge1$;不独立时不能乘 CDF。按 $m$ 个取值枚举,通用快速幂 $O(m\log n)$,浮点幂可按误差要求使用;模概率须分母可逆。 ### 16. 顺序统计量:先区分连续与离散 **识别**:第 $j$ 小的期望、保留最小若干个样本的期望;动态过程可证明始终只保留历史的前几个小值。 **转化与应用**:对 $N\ge1$ 个独立连续均匀 $[0,m]$ 样本($m>0,1\le j\le r\le N$),排序后 $X_{(j)}$ 满足 $$E[X_{(j)}]=\frac{jm}{N+1},\qquad E[\sum_{j=1}^r X_{(j)}]=\frac{mr(r+1)}{2(N+1)}.$$ 可以把两端点也加入,$N+1$ 段间距由对称性具有相同期望;正式分布推导见 [MIT 18.443 顺序统计讲义](https://ocw.mit.edu/courses/18-443-statistics-for-applications-spring-2015/06daf6d78e7eb0465d6bb53e8f96b2ff_MIT18_443S15_LEC11.pdf)。 **小例**:3 个 $[0,8]$ 样本最小两个的期望和是 $8(1+2)/4=6$。 **前提与代价**:离散分布会并列,不能照搬均匀间距。整数 $[1,m]$ 中第 $j$ 小值可用尾和:$P(X_{(j)}>t)=\sum_{h=0}^{j-1}\binom Nh(t/m)^h(1-t/m)^{N-h}$。例 $N=2,m=2$ 的最小值期望是 $5/4$,不是连续公式 $2/3$。先证明“历史样本中第几小”的不变量、数清已生成样本总数,再套公式;连续闭式 $O(1)$,离散直接枚举约 $O(mj)$。 ### 17. 期望 DP:自环移项前先问是否有限 **识别**:随机重复操作直到终止;某次尝试可能不改变状态;问平均操作次数。 **转化与应用**:令 $E_s$ 为从 $s$ 到结束的未来期望代价,一步费用 $c_s$,终态为 0: $$E_s=c_s+p_0E_s+\sum_{t\ne s}p_{st}E_t, \qquad E_s=\frac{c_s+\sum_{t\ne s}p_{st}E_t}{1-p_0}.$$ 先确认除自环外有拓扑顺序,再 DP;无自环的“每次增加一个计数”模型见 [ABC184 D 官方题解](https://atcoder.jp/contests/abc184/editorial/371?lang=ja)。 **小例**:每次一半概率成功终止、一半留在原状态,$E=1+E/2$,故 $E=2$。若从 A 一步必到 B,B 一半结束、一半回 A,则 $E_A=1+E_B,E_B=1+E_A/2$,得 $E_A=4$;这已经不能只移掉局部自环。 **前提与代价**:$p_0=1$ 的正费用状态期望无穷;有限状态吸收链也要排除可达的非终止闭类。一般 SCC 可建立线性方程,$s$ 个状态朴素 $O(s^3)$,有向无环依赖则 $O(\#状态+\#转移)$。若求终止概率,常数项与边界不同,不能套步数方程。 ### 22. 分类期望:不要漏掉被状态改变的另一类 **识别**:随机排列中,达到第 $a$ 个特殊对象后规则改变;“在阈值之前/之后”的对象贡献不同。 **转化与应用**:先固定一个对象,计算它位于阈值之后的概率,再把同类权重求和。设有 $c\ge a\ge1$ 个特殊对象和若干普通对象,均匀随机排列,到第 $a$ 个特殊对象时屏障消失,该对象本身仍被屏障挡住。特殊权重和 $S$ 中,只有后 $c-a$ 个起作用,期望 $S(c-a)/c$。 某个普通对象与 $c$ 个特殊对象的相对次序均匀,所在 $c+1$ 个间隙等概率;屏障后有 $c-a+1$ 个间隙,所以其作用概率为 $(c-a+1)/(c+1)$,普通权重和 $W$ 贡献 $W(c-a+1)/(c+1)$。 **小例**:$c=a=1$,特殊权重 10,普通权重 4。两种相对次序中只有“特殊、普通”产生 4 的贡献,期望 2;特殊自身贡献为 0。 **前提与代价**:阈值对象是否生效、未达到阈值如何处理、排列是否等概率,都会改变式子;$a=0$ 应全量生效而不是套原分类;$c<a$ 时本模型屏障始终存在。分类计数 $O(n)$,按阈值有多次询问时可排序、前缀和。思想与 36 的指示变量一致,不能把此特定规则当成通用伤害公式。 ### 36. 期望的贡献法:相关事件也能逐项求和 **识别**:问不同颜色数、空盒数、逆序对数、被覆盖点数;整体分布很大,但一个对象是否被计入容易求概率。 **转化与应用**:给每个对象定义 $I_i=[\text{它被计入}]$,则 $E[\sum I_i]=\sum P(I_i=1)$,不要求 $I_i$ 之间独立。独立投入 $m$ 个球、每球等概率选 $n$ 个盒子,空盒期望 $n(1-1/n)^m$。 **小例**:3 球入 2 盒,期望空盒数 $2(1/2)^3=1/4$;两个盒子的空事件不独立,线性求和仍正确。 **应用与前提**:[CSES Moving Robots](https://cses.fi/problemset/task/1726) 可先对每个起点做随机游走 DP 得到终点概率 $p_{s,t}$,再算空格概率 $\prod_s(1-p_{s,t})$,最后对格子 $t$ 求和。这个乘积要求不同机器人的游走独立,而最后一层求和不要求各格子独立。$V$ 格、$E$ 条可走边、$k$ 步,逐起点计算为 $O(VkE+V^2)$;不能用“进入格子的期望个数为 0”代替“格子为空的概率”。 ### 37. 收集和等待:按“下一次取得进展”分阶段 **识别**:重复抽样直到见到新种类、集齐全部、凑够若干次成功;无效尝试会原地停留。 **转化与应用**:独立同分布试验成功概率为 $p>0$,包含最终成功的一共尝试次数期望为 $1/p$。如果目前已集齐 $k$ 种、总共 $n$ 种等概率,那么下一次新种类概率是 $(n-k)/n$,该阶段等待期望 $n/(n-k)$,总计 $nH_n$。分阶段推导见 [MIT 6.856 Coupon collecting 讲义](https://ocw.mit.edu/courses/6-856j-randomized-algorithms-fall-2002/2e00cd3ccdd9e9e9aa3f4b8305a6abef_n4.pdf)。 **小例**:3 种等概率卡片,收集齐期望 $1+3/2+3=11/2$ 次。成功概率 $1/4$ 时,成功前失败次数期望为 3,包含成功则为 4。 **前提与代价**:若种类不等概率,仅知道“已收集多少种”不能决定下一次进展概率,可能要记录具体集合;试验概率随失败变化也不再是固定几何分布。等概率求和 $O(n)$,重复 $r$ 次固定成功且每次条件不变为 $r/p$。几何变量从 0 还是 1 开始取值必须写清。 ## 五、优化:用差分证明最优点在哪里 ### 18. 绝对值:拆方向、找中位数、看顺序 **识别**:把所有数改成同一个数的代价是绝对差;一维移动、相邻交换聚拢、两两距离求和。 **转化与应用**:$F(x)=\sum_i|a_i-x|$ 的斜率是左侧数量减右侧数量,故中位数处最小;有正权重时换成左右权重,取加权中位数。固定 $x$ 还可排序加前缀和求值。[CSES Stick Lengths](https://cses.fi/problemset/task/1074) 是直接应用。 **小例**:$[1,2,2,3,5]$ 取 $x=2$,代价 $1+0+0+1+3=5$。 **扩展与前提**:保持顺序的位置 $p_1<\cdots<p_k$ 要移成连续格 $x+1,\ldots,x+k$,先令 $b_i=p_i-i$,再找 $b$ 的中位数。例 $p=[1,4,6]$,$b=[0,2,3]$,选 $x=2$,目标 $[3,4,5]$,代价 3。移动费用是平方差时最优点是均值附近,不能用中位数。排序 $O(n\log n)$,选择中位数可期望 $O(n)$。 ### 19. 分段线性函数:扫断点,不猜单峰 **识别**:代价有 $\max(0,x-a)$、$\min(x,b)$、截断区间长度,参数是一维整数或实数。 **转化与应用**:每一项只在少数断点改变斜率,排序事件后维护当前值与斜率。对 $$F(t)=x t+y\sum_i\max(0,r_i-\max(l_i,t)),\quad t\ge0,$$ 在不含端点的开区间里,斜率 $x-y\cdot\#\{i:l_i<t<r_i\}$。在 $l_i$ 处减 $y$,在 $r_i$ 处加 $y$,区间内线性,故只需检查端点及定义域边界。 **小例**:$x=1,y=2,[l,r]=[2,5]$,$F(0)=6,F(2)=8,F(5)=5$。先增、再减、再增,不能仅凭 `max` 就断言凸或直接三分。 **前提与代价**:接口 `cp::clipped_cost_min(x,y,intervals)` 对应以上精确公式,要求 $x,y\ge0$,端点合法,返回整数 $t$ 的最优值和位置。一次排序 $O(n\log n)$,用 i128 推进 $value+=slope\cdot\Delta t$。换一个式子须重推每个事件的斜率增量;同坐标事件合并处理。 ### 38. 排列怎样配对最优:计算一次交换的差 **识别**:两个序列可重排配对,目标是乘积和或某种总惩罚;直觉是“大配大”但缺证明。 **转化与应用**:先比较两个位置的两种配法。若 $a\le b,c\le d$,有 $$ac+bd-(ad+bc)=(b-a)(d-c)\ge0.$$ 所以乘积和同向排序最大、反向排序最小;反复消去逆序配对就得到全局证明。实数可含负数,关键是两个差同号。 **小例**:$[1,4]$ 与 $[2,7]$,同向和为 30,反向为 15,差 $(4-1)(7-2)=15$。若最小化平方差,展开 $\sum(a_i-b_{\pi(i)})^2$ 后只有 $-2\sum a_ib_{\pi(i)}$ 受排列影响,所以同向配对最小。 **前提与代价**:只适用于目标可按成对交换比较且任意配对合法。存在禁配边、额外跨位置项时,排序结论未必成立,可能回到匹配/DP。通常排序 $O(n\log n)$。上面的等式就是独立完整证明,使用前先写出自己题目的交换差,不能只记“大配大”。 ### 39. 总量固定如何分配:凸性等价于边际费用递增 **识别**:固定总和,最小化平方和、负载惩罚、分配资源;每多分配一个单位代价会改变。 **转化与应用**:对整数费用 $f$ 定义边际 $\Delta f(x)=f(x+1)-f(x)$。若边际随 $x$ 非降,将一个单位从较大负载移向较小负载不会变差;同一种凸费用、无额外约束时,最优各份最多差 1。不同凸费用 $f_i$ 可从满足下界的配置出发,每次选择最便宜的下一单位,用堆维护边际。 **小例**:$x+y+z=8,x,y,z\ge0$,最小平方和在 $[2,3,3]$,为 22。若某两项相差至少 2,$a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1)>0$,因此一定还能改进。 **前提与代价**:异权费用并不要求负载尽量相等;取整、容量上下界要进入可行域。边际不单调时,逐单位堆贪心可能错。相同费用直接均分 $O(n)$;分配 $K$ 个增量的堆法 $O((n+K)\log n)$。本条采用显式交换证明,不需要浮点求二阶导数。 ## 六、结构与不变量:先决定历史能压缩成什么 ### 7. 分组 DP:余数能算出来就不存 **识别**:选完一个集合之后分组,组目标和相同;DP 同时记录已选 `mask` 和当前桶内和。 **转化与应用**:在每组和固定为 $T>0$、非负数装桶且当前组和不超过 $T$ 的模型中,当前余数由 $$rem(mask)=\left(\sum_{i\in mask}a_i\right)\bmod T$$ 唯一决定。只记录 `reachable[mask]`;尝试加入未选元素时检查 $rem+a_i\le T$。可预处理子集和,或者递推到达时携带唯一余数。 **小例**:$[1,1,2,2]$ 分成两个和为 3 的组。选过一个 1、一个 2 时总和 3,余数 0;不同加入次序不需要不同状态,下一组从空桶开始。 **前提与代价**:还要有总和是 $T$ 的倍数、目标组数一致等整体条件;负数时不能用“不超桶容量”剪枝。零元素与非空组要求单独核对。若还有组大小、顺序、颜色限制,余数仍可推导但其他信息可能不能删除。复杂度 $O(n2^n)$、空间 $O(2^n)$;这里的删维来自公式,不代表所有分组问题都能这么转移。 ### 23. 区间数量比较 → 前缀差 → 多维偏序 **识别**:一个区间里 A 的数量至少 B、同时至少 C;求若干不交合法区间的总长最大。 **转化与应用**:定义 $X_i=\#A-\#B,Y_i=\#A-\#C$ 的前缀值,则 $(j,i]$ 合法当且仅当 $X_j\le X_i,Y_j\le Y_i$。若 $dp[i]$ 为前 $i$ 个位置的最优覆盖总长, $$dp[i]=\max\bigl(dp[i-1],\ i+\max_{j<i,X_j\le X_i,Y_j\le Y_i}(dp[j]-j)\bigr).$$ 按时间从左到右,用二维前缀最大值保存坐标 $(X_j,Y_j)$、权 $dp[j]-j$。 **小例**:字符串 ABB 的前缀坐标为 $(0,0),(1,1),(0,1),(-1,1)$。AB 合法,ABB 因 A 少于 B 不合法,最大覆盖为 2。 **前提与代价**:接口 `cp::Fenwick2DMax`,提前提供所有可能更新坐标,单次更新/查询 $O(\log^2 n)$、总空间 $O(n\log n)$。先查询再插入当前点以保持 $j<i$;严格不等改压缩下标边界。只支持 `chmax`,不能删点或把权值降低。若允许重叠区间,以上 DP 的含义需要改变。 ### 24. 树上端点差分:用割证明方向 **识别**:树上给很多条路径,问每条边经过次数或奇偶;逐路径走太慢。 **转化与应用**:固定树边,删去后树分成两块。一条路径经过此边,当且仅当其端点分别在两块。因此奇偶模型对每条路径做 $d_u\mathrel{\char94}=1,d_v\mathrel{\char94}=1$,自底向上异或子树,边 $(fa,v)$ 的答案就是汇总后的 $d_v$。 **小例**:路径树 $1-2-3$ 上加入 $(1,3)$ 与 $(1,2)$ 两条路径,边 $1-2$ 被过两次,奇偶为 0;边 $2-3$ 一次,奇偶为 1。 **前提与代价**:这是边覆盖;若数实际次数,使用 $d_u++,d_v++,d_{lca}-=2$ 再子树求和。点覆盖则为 $d_u++,d_v++,d_{lca}--,d_{fa(lca)}--$,根父亲为虚点;模型不同,修正点不同。奇偶接口 `cp::tree_path_xor_edges` 不需要 LCA,$O(n+q)$;实际计数加 LCA 预处理约 $O((n+q)\log n)$。 ### 40. 不变量与势能:证明不可能,再界定操作次数 **识别**:要求构造操作序列或证明无法到达;每步只改少数位置,直接搜索的状态过大。 **转化与应用**:先求一个在操作下保持的量,如总和、奇偶、棋盘染色差、置换符号;这给出必要条件。若要证明过程会停止,找非负整数势能 $\Phi$,证明每步至少下降 1。必要条件不自动是充分条件,仍需构造能达到目标。 **小例**:黑白染色棋盘上每块多米诺覆盖一黑一白,因此黑白数量不同必不能铺满;数量相同也未必能铺满带洞棋盘。排序时每次交换一对相邻逆序,逆序数恰减 1,所以最多初始逆序数次停止。$[3,1,2]$ 有 2 个逆序,恰需 2 次相邻交换。 **前提与代价**:计数势能应保证有下界;实数严格下降但每次降幅可能趋于 0,不足以推出有限步终止。多米诺的标准完整矩形模型可练 [CSES Counting Tilings](https://cses.fi/problemset/task/2181),不要把必要染色条件当完整计数算法。逆序数可树状数组 $O(n\log n)$;势能还可用于证明摊还复杂度,而不是要求实际模拟全部操作。 ### 41. 非单调也能找零点:离散介值保持的是异号括区 **识别**:要求找到某个平衡位置;函数可能反复波动,但每移动一个位置只变 $-1,0,1$,两端一负一正。 **转化与应用**:设整数函数满足 $|f(i+1)-f(i)|\le1$,已知 $f(L)<0<f(R)$。取中点 $M$,若为 0 立即返回;若负,保留 $[M,R]$;若正,保留 $[L,M]$。每次只维护两端异号,离散介值保证区间内仍有一个 0,不要求全局单调。 **小例**:$[-2,-1,0,-1,0,1,2]$ 不单调。两端异号,中点值 $-1$,保留右半;新中点可取值 0 的位置,找到一个解。 **前提与代价**:只能保证找“某个”零点,不能保证最早零点;若相邻可从 $-1$ 跳到 $+1$,零点不再必然存在。要严格证明每次相邻变化界,以及一个已知异号初始区间。本段是根据相邻变化界直接给出的证明;评估一次函数为 $T$,查询复杂度 $O(T\log(R-L))$。 ## 21. 赛时落地的五步 1. **写量**:明确元素、位置、下标集合、概率事件分别是什么;先把题意变成一个等式或不等式。 2. **找宽条件**:精确 GCD 改成倍数条件,最大值改成 CDF,复杂选择改成固定对象的贡献。 3. **证明压缩**:说明删掉的信息为什么不影响后续决策;对不变量用归纳,对最优策略用交换差或上下界。 4. **匹配计算规模**:值域能否筛、状态能否 $2^B$、卷积长度能否容纳、模数是否允许求逆;再选择接口。 5. **算一个小例**:至少独立手算一个能区分模型的例子,再核对程序的初始化、计数对象与边界。分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 22 天
部分内容可能已过时