【一车板子】CSP-S考前模板速记

提高组模板复习，需要同时记住模型的成立条件、维护量和可修改的边界。区间加扩展到乘加，标记就有先后顺序；最短路扩展到次短路，需要重新定义等长路径是否计入；并查集能判断连通，却不能代替割点、桥和强连通分量。

基础工具：把前提和语义一起记

• 整数二分先证明真假只切换一次。找首个真时，中点向下取整，真则保留左半区间，假则删去中点及其左侧；无解哨兵不参与判定。对答案二分还要分别证明判定算法正确，含负数的分段和不能直接用“超限就切段”的贪心。
• 前缀和查询闭区间用 s_r−s_l−1；差分给 [l,r] 加值，改变 l 和 r+1，最后求前缀恢复。二维情形用四个角的容斥。离散化只保序，区间长度保留原坐标。
• 归并计逆序对时，右侧元素严格更小才增加左侧剩余项数，相等不计；归并前两段应分别有序。快排划分要让相等元素也能推动指针，随机化或三路划分可缓解重复值退化；sort 的比较函数必须满足严格弱序，不能使用小于等于。堆排序为 O(nlog⁡n)，桶排序要计入值域；基数排序每轮按位稳定分配，总时间与位数、桶数共同有关。
• 分治的合并结果必须能从子问题恢复；递归式 T(n)=2T(n/2)+O(n) 对应 O(nlog⁡n)。双端栈共用数组时注意两端相遇，堆只保证堆顶最值；multiset.erase(value) 会删除全部同值项，要删除一次需先找迭代器。迭代器失效、递归调用栈和 bitset 的按机器字并行成本都计入实际实现。
• 高精度数组通常低位在前，加法带进位、减法先比较绝对值，乘法逐位累加后统一进位。除以正整数时反向扫描，用“旧余数乘进制加当前位”求商；中间值也需放得下。结束后去前导零，零保留一位；符号与绝对值运算分开。

数据结构

单调结构与 ST：能丢弃哪些候选

滑动窗口最小值的队列存下标：先弹出过期位置，再弹出队尾不小于新值的位置，最后入队。被删除的旧值不小于新值，且更早过期，以后不会胜过新值。每个下标入队、出队各一次，总时间为 O(n)。

统计以第 i 项为最小值的子数组，需约定重复值归属。设左边界 L_i 为左侧首个严格更小的位置，右边界 R_i 为右侧首个小于等于的位置，则贡献为 (i−L_i)(R_i−i)，相同最小值归最右位置。两边都严格会重复计数，两边都非严格会漏掉跨越重复值的区间。

静态区间最小值可用 ST。f[i][j] 覆盖从 i 起、长度为 2^j 的区间，L 满足 2^L>n。

int lg[N], f[N][L];void ini() {    for (int i = 2; i <= n; i++) {        lg[i] = lg[i / 2] + 1;    }    for (int i = 1; i <= n; i++) {        f[i][0] = a[i];    }    for (int j = 1; j < L; j++) {        for (int i = 1; i + (1 << j) - 1 <= n; i++) {            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);        }    }}int ask(int l, int r) {    int k = lg[r - l + 1];    return min(f[l][k], f[r - (1 << k) + 1][k]);}

查询两块可以重叠，合并运算须满足结合律和幂等性 x∘x=x。最值、最大公约数、按位与或可用；区间和、异或不能这样查询。预处理时间、空间均为 O(nlog⁡n)，每次查询只需常数时间。

两棵树状数组：从差分还原前缀和

令 d_i=a_i−a_i−1，则

两棵树分别维护 d_i、(i−1)d_i。区间加仅改变差分的两个端点；下面初始数组为零。

ll t1[N], t2[N];void add(ll *t, int p, ll v) {    for (; p <= n; p += p & -p) {        t[p] += v;    }}void chg(int l, int r, ll v) {    add(t1, l, v);    add(t1, r + 1, -v);    add(t2, l, (l - 1) * v);    add(t2, r + 1, -r * v);}ll pre(int p) {    ll s = 0;    for (int i = p; i > 0; i -= i & -i) {        s += p * t1[i] - t2[i];    }    return s;}

闭区间和为 pre(r) - pre(l - 1)，单次操作为 O(log⁡n)。有初值可逐点调用 chg(i, i, a[i])。更新下标须为正，查询零合法；右端为 n 时，更新 n+1 被循环跳过。类型须容纳加权差分与区间和。

仿射懒标记：新变换复合在旧变换之后

区间乘、区间加统一写成 x←ax+b(modP)。sm 是已计入标记的区间和，旧标记表示 x↦Mx+A；再施加新变换后为 x↦aMx+aA+b。系数已归一化，2≤P≤2×10⁹，并保证乘积与区间长度乘法在 ll 内。

ll sm[N * 4], ml[N * 4], ad[N * 4];void app(int u, int l, int r, ll a, ll b) {    sm[u] = (sm[u] * a + b * (r - l + 1)) % P;    ml[u] = ml[u] * a % P;    ad[u] = (ad[u] * a + b) % P;}void ps(int u, int l, int r) {    int m = l + (r - l) / 2;    app(u * 2, l, m, ml[u], ad[u]);    app(u * 2 + 1, m + 1, r, ml[u], ad[u]);    ml[u] = 1;    ad[u] = 0;}

建树时每个使用节点的乘标记均设为一，加标记为零，叶子存原值，父亲合并孩子。修改完整覆盖就调用 app；部分覆盖先 ps，再递归有交集的孩子，最后重新合并。查询完整覆盖返回 sm，否则先下传再合并查询结果；不对叶子调用 ps。单次操作为 O(log⁡n)，空间为 O(n)。

“先加 3 再乘 2”的标记是 (2,6)，“先乘 2 再加 3”是 (2,3)。单位标记为 (1,0)；区间赋值也可表示为 (0,b)。下传必须沿用同一个复合顺序，不能只更新区间和、忘记孩子已有的标记。

扫描线：线段树维护实际覆盖长度

求轴平行矩形并面积，把左右边分别转成加入、删除纵区间的事件。去重后的纵坐标为 y₁<⋯<y_k，线段树叶子 i 代表 [y_i,y_i+1)，因此只有 k−1 片。更新 [y_a,y_b) 对应叶子区间 [a,b−1]，长度不能用排名差代替。

cnt[u] 仅记录完整覆盖本节点的活动区间数，len[u] 是该段实际被覆盖的长度，合并规则为：

void pu(int u, int l, int r) {    if (cnt[u] > 0) {        len[u] = y[r + 1] - y[l];    } else if (l == r) {        len[u] = 0;    } else {        len[u] = len[u * 2] + len[u * 2 + 1];    }}

完整覆盖时只增减当前 cnt，部分覆盖递归孩子，返回时均调用 pu。这里不把 cnt 下传：即使父亲暂时被整体覆盖，孩子仍保留自己的覆盖记录，父亲计数归零后便能恢复它们的长度。

按横坐标分组，先累加“上一组处理后的覆盖长度乘横坐标差”，再处理当前组全部事件。忽略零面积矩形，核算面积乘法范围。总时间为 O(nlog⁡n)，空间为 O(n)。

笛卡尔树：中序顺序与堆序同时满足

以数组下标为中序、数值为小根堆序，区间最小值就对应该区间两端在树上的 LCA。以下将相等值中靠左者作为祖先，构造前清零左右孩子，st 始终保存当前树的右侧祖先序列。

int lc[N], rc[N], st[N], tp = 0;for (int i = 1; i <= n; i++) {    int q = 0;    while (tp > 0 && a[st[tp]] > a[i]) {        q = st[tp--];    }    if (tp > 0) {        rc[st[tp]] = i;    }    lc[i] = q;    st[++tp] = i;}int rt = st[1];

被弹出的最后一棵子树整体移到新节点左侧，新节点接替剩余栈顶原来的右孩子，所以中序仍为原下标顺序。每个位置入栈、出栈各一次，构造为 O(n)；树仍可能退化成链，后续遍历需考虑递归深度。若把比较改为大于等于，相等值的归属会变成靠右者，相关区间边界也要统一。

FHQ Treap：分裂后再按中序合并

维护可重复键的有序多重集合，每次出现各占一个节点，中序非降，随机优先级维持堆序。sp 按阈值分裂：eq == false 时左树键严格小于 v，为真时左树键小于等于 v，避免写 v - 1 引起下溢。

ll vl[N];int lc[N], rc[N], sz[N], tot;unsigned rd[N];mt19937 rng(712367);void pu(int p) {    sz[p] = sz[lc[p]] + sz[rc[p]] + 1;}int crt(ll v) {    int p = ++tot;    vl[p] = v;    rd[p] = rng();    sz[p] = 1;    return p;}void sp(int p, ll v, bool eq, int &x, int &y) {    if (p == 0) {        x = y = 0;        return;    }    if (vl[p] < v || (eq && vl[p] == v)) {        x = p;        sp(rc[p], v, eq, rc[p], y);    } else {        y = p;        sp(lc[p], v, eq, x, lc[p]);    }    pu(p);}int mg(int x, int y) {    if (x == 0 || y == 0) {        return x + y;    }    if (rd[x] < rd[y]) {        rc[x] = mg(rc[x], y);        pu(x);        return x;    }    lc[y] = mg(x, lc[y]);    pu(y);    return y;}

零号节点大小为零，新节点孩子为零；不回收编号时，容量按插入总次数开。mg(x,y) 要求左树所有键不大于右树所有键，不能合并任意两棵搜索树。

插入值 v：sp(rt, v, true, a, b)，再令 rt = mg(mg(a, crt(v)), b)。删除一次：先按严格小于 v 拆出左树，再把剩余树按小于等于 v 拆出相等部分；相等树非空时，用其根的两个孩子合并后替换该根，最后按原顺序合并三部分。重复值只删除一个节点。

排名定义为“小于 v 的数的个数加一”，按严格小于分裂后取 sz[a] + 1，查询后恢复根。查第 k 小，比较 k 与左孩子大小：等于左大小加一就返回当前键，小则向左，大则减去左大小加一后向右；要求 1≤k≤sz[rt]。随机独立优先级下操作期望为 O(log⁡n)，不能把期望复杂度写成最坏保证。

字符串

Trie 与哈希：保存的对象不同

普通 Trie 按字符走边。每经过一个节点增加前缀计数，单词结束处另增终止计数；前者回答“多少次插入以此为前缀”，后者回答“这个单词出现几次”。删除前确认单词存在，沿原路径减计数；只标记终点会把前缀查询写错。字符集大小为 Σ 时，稠密孩子数组占用 O(Σ∑|s|) 空间，单次操作为 O(|s|)。

01 Trie 把整数按固定最高位到最低位存入两叉树。查询最大异或时，优先走与当前位相反且计数非零的孩子，因为高位贡献超过所有更低位之和；删除后不能只看指针存在。位宽应覆盖全部数据，移位采用相应无符号类型，单次操作为 O(B)。

字符串多项式哈希维护 H_i=H_i−1b+c_i(modP) 与 Q_i=bⁱmodP，子串值为 H_r−H_l−1Q_r−l+1，归一化后可在 O(1) 时间比较等长子串。相等哈希不能证明字符串相等；双模数只能降低碰撞风险，处理哈希表冲突仍须比较原键。

KMP 的 π_i 表示截至位置 i 的最长相等真前后缀长度。失配时反复令 j←π_j−1，保留仍可能成为匹配的后缀；完整匹配后同样回退，才能找到重叠出现并避免访问模式串尾后。模式串不能为空。文本、模式预处理与扫描总时间为 O(|s|+|t|)，额外空间为 O(|t|)。

Manacher：半径的定义决定还原公式

插入统一分隔符后，奇偶长度回文可以一起处理。下面把原字符转成非负整数，用负数作分隔符和左右哨兵，避免哨兵与输入字符相同。p[i] 包含中心，回文在变换串中覆盖 [i−p_i+1,i+p_i−1]；r 是已知回文的右端后一位。

int n = (int)s.size();vector<int> t(n * 2 + 3, -1), p(n * 2 + 3);t[0] = -2;t[n * 2 + 2] = -3;for (int i = 0; i < n; i++) {    t[i * 2 + 2] = (unsigned char)s[i];}int c = 0, r = 0, ans = 0;for (int i = 1; i <= n * 2 + 1; i++) {    p[i] = i < r ? min(p[c * 2 - i], r - i) : 1;    while (t[i - p[i]] == t[i + p[i]]) {        p[i]++;    }    if (i + p[i] > r) {        c = i;        r = i + p[i];    }    ans = max(ans, p[i] - 1);}

对落在已知回文内的中心，镜像半径只有不越过右边界的部分可以直接继承，超出部分仍要比较。右边界只向右移动，成功扩展总次数为 O(n)。原串最长回文长度为 ans；某中心对应原串起点为 (i - p[i]) / 2，长度为 p[i] - 1，起点使用零下标，空串也可处理。

图论

邻接表遍历 O(n+m)，矩阵遍历 O(n²)。无权最短路用 BFS，入队即标记；DFS、BFS 须遍历每个连通块。片段独立，编号 1∼n，数组每组清空。距离用 ll；INF 大于有限答案，有限值相加不得溢出。

最小生成树：Prim 与 Kruskal

Prim 维护到已选点集的最小边权，更新 d_v←min(d_v,w_uv)，不加 d_u。起点置零，每次选未入树且 d 最小的点；选不到有限值则不连通。朴素实现 O(n²+m)，堆实现 O((n+m)log⁡(n+m))。

Kruskal 按边权递增枚举，并查集不同才合并、计权；选满 n−1 条才有生成树，否则为最小生成森林。时间 O(n+mlog⁡(m+1))。自环不选，重边可留，负权允许。割性质保证轻边可替换生成树跨同一割的较重边。最短路树与最小总边权不能混用。

单源最短路与严格次短路

Dijkstra 要求非负边权，允许零边。弹出距离与当前标签不同则丢弃；第一次入堆时距离尚未定案。

Bellman–Ford 置源点距离零，至多扫描全部边 n−1 轮，只从有限距离松弛；第 n 轮仍能改进，说明有源点可达负环。仅负环之后可达的点失去有限最短距离。SPFA 只让改变过的点继续松弛，最坏仍为 O(nm)。判负环可随松弛继承路径边数 cnt[v] = cnt[u] + 1，达到 n 即停止；不能换成任意总更新次数。查全图负环时，增设向每点连零边的超级源。

严格次短的长度必须大于最短长度。下面允许重复点、边，即求 walk。例如，一条无向边的权值为一：两端最短长度为一，往返后再到达则长为三，这是严格次短 walk，第二条简单路径却不存在。等长的另一条最短路也不计入。

e[u] 保存 (v,w)；d[u][0]、d[u][1] 存两种最小长度，INF 表示不存在。

void dij(int s) {    for (int i = 1; i <= n; i++) {        d[i][0] = d[i][1] = INF;    }    priority_queue<pair<ll, int>, vector<pair<ll, int>>,        greater<pair<ll, int>>> q;    d[s][0] = 0;    q.push({0, s});    while (!q.empty()) {        ll k = q.top().first;        int u = q.top().second;        q.pop();        if (k != d[u][0] && k != d[u][1]) {            continue;        }        for (auto t : e[u]) {            int v = t.first;            ll z = k + t.second;            if (z < d[v][0]) {                swap(z, d[v][0]);                q.push({d[v][0], v});            }            if (d[v][0] < z && z < d[v][1]) {                d[v][1] = z;                q.push({z, v});            }        }    }}

换下来的旧最短还要竞争次短。同一点的第三种长度可舍弃：接相同后缀，已有两种更小前缀给出两种更小总长度。每点只需保留两种不同的有效长度，旧记录和同值重复只造成常数次额外扩展；时间 O((n+m)log⁡(n+m))，堆空间 O(n+m)。零权环不产生新长度。

Floyd、拓扑序与二分图

Floyd 初始化对角线零、不可达项 INF，重边取小。中转点 k 在最外层，再枚举 i,j，两段可达才更新 d_ij←min(d_ij,d_ik+d_kj)。第 k 轮允许的内部顶点为前 k 个点，因此可原地更新；时间 O(n³)、空间 O(n²)。若 d_kk<0，经过该负环的可达点对不存在有限最短路。

拓扑排序让所有入度零点入队；弹出 u 后删每条出边，邻点入度降为零再入队。弹出不足 n 点即有环。DAG 最长路先置 f_s=0、其余为负无穷，在拓扑序中仅从可达点执行 f_v←max(f_v,f_u+w_uv)；删除边和减入度不能受可达性判断控制。所有前驱都处理完才处理当前点，负权边也可用。排序、转移共 O(n+m)。

二分图染色遍历每个连通块，沿边令 c_v=1−c_u；遇同色邻点即失败，自环立即冲突。树深度奇偶给出颜色，冲突边与树路径构成奇环；无奇环则无冲突，时间 O(n+m)。

欧拉道路：先验度数，再取边

无向图只看非零度顶点，它们须连通；欧拉回路要求所有度数为偶数，非闭合道路要求恰有两个奇度点，并从其中一个出发。自环贡献两度。

有向图要求非零度顶点忽略方向后连通。回路各点出入度相等；非闭合道路起点出度多一、终点入度多一，其余相等。从规定起点出发；回路任选有出边的点。终点向起点补边得到平衡图，Hierholzer 不断把未用回路接入已有行走。

邻接项为 (v,id)。无向边两项共用物理边 ID，有向边各有独立 ID；vis[id] 标记整条边，ptr[u] 保证只扫描一次。m 为物理边数。

vector<int> eul(int s) {    vector<int> st(1, s), ans;    while (!st.empty()) {        int u = st.back();        while (ptr[u] < e[u].size() && vis[e[u][ptr[u]].second]) {            ptr[u]++;        }        if (ptr[u] == e[u].size()) {            ans.push_back(u);            st.pop_back();        } else {            auto t = e[u][ptr[u]++];            vis[t.second] = 1;            st.push_back(t.first);        }    }    if (ans.size() != m + 1) {        return {};    }    reverse(ans.begin(), ans.end());    return ans;}

退栈时加入答案，最后反转。长度不足 m+1 说明漏边，但长度检查不能代替度数条件。无边时任选合法顶点。时间、空间 O(n+m)。

强连通分量：两种低链更新

Tarjan 的 dfn 为发现次序，low 维护沿 DFS 子树与栈内边可回到的早期位置。树边回溯取 low[v]；栈内已发现点取 dfn[v]，出栈点不参与。st 为栈，ins 标记在栈，bel 为分量编号。

void scc(int u) {    dfn[u] = low[u] = ++tim;    st[++top] = u;    ins[u] = 1;    for (int v : e[u]) {        if (!dfn[v]) {            scc(v);            low[u] = min(low[u], low[v]);        } else if (ins[v]) {            low[u] = min(low[u], dfn[v]);        }    }    if (dfn[u] == low[u]) {        tot++;        int v;        do {            v = st[top--];            ins[v] = 0;            bel[v] = tot;        } while (v != u);    }}

枚举未发现点。dfn[u] == low[u] 时，从栈顶弹出至当前点，得到分量。跨分量边连 bel[u] -> bel[v]，缩点必为 DAG，否则环上分量应互相可达。平行边按同一种转移计数时去重，按物理边区分方案时保留。时间、空间 O(n+m)。

割点与割边：等号不能混

无向图沿树边 u→v 回溯：low_v>dfn_u 时该边为桥，low_v≥dfn_u 时非根顶点 u 为割点。前者回不到 u，后者删 u 后回不到祖先。根单独看树孩子数，大于一才是割点。

邻接项 (v,id)，物理边共用 ID；递归传入入边 ID，只跳过这条边，不能跳过所有通向父节点的边，否则两条平行边会被误判成桥。

void dfs(int u, int id) {    dfn[u] = low[u] = ++tim;    int cnt = 0;    for (auto t : e[u]) {        int v = t.first, j = t.second;        if (j == id) {            continue;        }        if (!dfn[v]) {            cnt++;            dfs(v, j);            low[u] = min(low[u], low[v]);            if (low[v] > dfn[u]) {                bri[j] = 1;            }            if (id != -1 && low[v] >= dfn[u]) {                cut[u] = 1;            }        } else {            low[u] = min(low[u], dfn[v]);        }    }    if (id == -1 && cnt > 1) {        cut[u] = 1;    }}

每个未访问块调用 dfs(s, -1)。割点、桥以删除后连通块数增加为准，孤立点不是割点。删去所有桥后的连通块构成边双连通分量；点双连通分量则可能在割点处相交，不能简单删除割点再把剩余块当作完整分量。时间、空间 O(n+m)；不能照搬 SCC 的栈内边规则。深链递归可达 n 层，须核算栈或显式保存回溯状态。

树

DFS 序、欧拉序与最近公共祖先

首次进入 u 令 tin_u=++tim，处理完孩子令 tou_u=tim，子树对应 [tin_u,tou_u]。计时器只在首次进入时增加；点权放到 tin 位置，子树和转为区间和，用前缀和或树状数组维护。

倍增设 f_u,0 为父亲，f_u,j=f_{fu,j−1,j−1}。根深度一、父亲零，零号整行置零；先填父亲表再处理孩子。取 2^L>n，层号 0∼L−1。

int lca(int a, int b) {    if (dep[a] < dep[b]) {        swap(a, b);    }    int k = dep[a] - dep[b];    for (int j = 0; j < L; j++) {        if ((k >> j) & 1) {            a = f[a][j];        }    }    if (a == b) {        return a;    }    for (int j = L - 1; j >= 0; j--) {        if (f[a][j] != f[b][j]) {            a = f[a][j];            b = f[b][j];        }    }    return f[a][0];}

对齐深度后，仅在祖先不同时同时上跳，始终停在 LCA 下方。预处理与空间 O(nlog⁡n)，查询 O(log⁡n)。根到点权和为 dis_u，距离为 dis_u+dis_v−2dis_lca(u,v)，负权也适用。

欧拉序 LCA：进入顶点、从孩子返回时均记录当前点，长度为 2n−1。两点首次位置间深度最小的顶点为 LCA，不取最小编号。稀疏表预处理 O(nlog⁡n)、查询 O(1)。此序列重复记录顶点，不能与子树 DFS 序混用。

重心、直径与树上差分

设子树大小为 siz_u，删点 u 后的最大块为 max(n−siz_u,max_v 为孩子siz_v)；不超过 n/2 的点为重心。重心与边权无关；有一个或相邻两个，后序统计需 O(n)。

非负权树求直径，从任一点遍历到最远点，再从该点遍历取最远距离，合计 O(n)；路径唯一，直接累计边权。负权时此法不成立：三点链边权 −100,5，从负边一端出发把自身当作最远点，漏掉权为 5 的直径。改用树 DP 合并向下路径；要求非空路径时答案初始负无穷，不能用零吞掉全负答案。

路径 u→v 加 w，令 p=lca(u,v)。点差分在 u,v 各加 w，在 p 和 p 的父亲各减 w，父亲为零时跳过。边差分在 u,v 各加 w、在 p 减 2w。修改后后序累加孩子差分到父亲：点差分得到点值；边差分的 d_u 对应父亲到 u 的边，根无对应边。LCA 处减一次还是两次，由点、边模型决定。共 q 次修改为 O(n+qlog⁡n)。

搜索：剪枝要能证明不会删掉答案

深搜中，可行性剪枝检查当前状态是否已经违反约束；最优性剪枝比较“当前代价＋剩余代价下界”与已知答案。下界必须不大于实际剩余代价；例如覆盖剩余需求至少还要两个操作，就不能因经验判断而写成至少三个。相同状态合并时，要保留影响后续选择的全部信息：已用集合、剩余资源、所在位置等。只按当前位置记忆化，可能把拥有不同剩余资源的状态混为一谈。

迭代加深按深度上限递增，每轮重新清理与该上限有关的访问记录；IDA* 用 g+h 控制上限，h 仍须是可采纳下界。A* 按 g+h 出队，不能首次入队就封死状态；若启发式不一致，需要允许更优代价重新进入。双向 BFS 适用于可逆或能构造反向转移的无权状态图，每次完整扩展一层并正确判断相遇距离，有向图的反向搜索应沿反边走。按较小边界扩展可以减小搜索量，不改变距离的层次定义。

动态规划：状态、转移与优化依据

背包、区间与多维状态

0/1 背包对容量倒序，完全背包对正体积物品正序；分组背包的同组候选统一读取上一组状态。计数时，物品在外通常统计无序组合，容量在外、枚举末项通常统计有序序列。恰好使用资源的模型只有零资源状态可达，其余置为负无穷或单独标记不可达；不能用零代替不可达后直接做加法。

二维资源背包的状态可设为 f[j][k]，0/1 物品对两个资源都倒序，时间为 O(nAB)。多维状态不是机械增加下标：每个维度应区分会改变后续转移的历史信息，能由其他量算出的维度可以删去。

相邻石子合并，设 f[l][r] 为把区间合成一堆的最小代价：

f[l][r]=min_l≤k<r{f[l][k]+f[k+1][r]}+s_r−s_l−1。

单点初值为零，按区间长度递增枚举，时间为 O(n³)、空间为 O(n²)。环形问题复制一遍序列，只计算长度不超过 n 的区间，最后在所有长度为 n 的区间中取答案。未经证明，不能直接限制决策点的搜索区间。

树形 DP 与换根

树上最大权独立集有两种状态：选当前点与不选当前点。对每个孩子，前者只能接“不选孩子”，后者取孩子两态的较大值。若所有权值为负，答案能否为零取决于是否允许空集。

树形背包设 f_u[j] 为当前已处理子树恰选 j 个点的最优值。合并孩子 v 时，转移为 g[j+k]=max(g[j+k],f_u[j]+f_v[k])；读取旧父数组或正确倒序，并检查两态均可达。若要求选点连通且包含 u，孩子选非空时才接入孩子根。朴素上界为 O(nm²)，剪去不超过子树大小的无效容量后，还要按实际合并范围重新核算。

换根的两遍处理分别解决“子树内部”和“子树外部”。例如无权树各点距离和，第一遍求子树大小和根的答案；从 u 换到孩子 v 时，v 子树内的点都近一，其余点都远一，所以

ans_v=ans_u+n−2sz_v。

带权边把增量乘以边权；带点权统计则把点数换成点权和。总时间为 O(n)。

状压与子集枚举

每点至多访问一次、访问集合和当前末点共同决定后续路线时，设 f[S][u] 为恰好访问集合 S、停在 u 的最小代价，向不在 S 中的点转移。一般完全图需要 O(n²2ⁿ) 时间和 O(n2ⁿ) 空间，位数与内存都要先核算。固定起点时，初始只有对应单点集合可达。

枚举非空子集可写成下面的循环；处理空集需要另列，不能让无符号或负数回绕决定终止。

for (int t = s; t > 0; t = (t - 1) & s) {    upd(s, t);}

所有集合及其子集一起枚举通常为 O(3ⁿ)，因为每个元素有“不在集合、在集合但不在子集、在子集”三种归属。将它误记成 O(2ⁿ) 会低估一整层枚举。

数位 DP 与记忆化边界

例如统计 [0,X] 中数位和能被 k 整除的整数。令 a 为十进制数位的逆序数组，dfs(p, s, lim) 表示剩余最高位为 p、已填数位和模 k 为 s、是否贴住上界。f 初始化为负一，只缓存不受上界限制的状态。

ll f[20][K];int a[20], k;ll dfs(int p, int s, bool lim) {    if (p < 0) {        return s == 0;    }    if (!lim && f[p][s] != -1) {        return f[p][s];    }    int r = lim ? a[p] : 9;    ll z = 0;    for (int d = 0; d <= r; d++) {        z += dfs(p - 1, (s + d) % k, lim && d == r);    }    if (!lim) {        f[p][s] = z;    }    return z;}

要求 1≤k<K，计数不超出 ll。前导零不改变数位和，所以这例不需要另记“是否开始”；若统计数字出现次数、相邻位限制或有效位数，前导零就可能改变含义，必须加状态或单独处理。零本身在这例中计入。区间答案用 F(R)−F(L−1)，约定负上界返回零。更换 k 或状态语义后清空记忆表；单次上界的时间为 O(log⁡X⋅k⋅10)。

常用优化先找转移结构

滚动数组要求旧层不再被其他转移读取。前缀和优化适用于连续区间上的加法汇总；单调队列适用于候选随窗口进入、过期且能按价值淘汰的转移。例如 f_i=v_i+max_{i−R≤j≤i−L}f_j，先加入 i−L，再删除小于 i−R 的下标，且不可达状态不进入队列。

LIS 维护每种长度的最小末尾，较小末尾能接上的后续元素包含较大末尾的选择；严格递增用 lower_bound，不下降用 upper_bound，尾值数组本身不保证是原序列的一条子序列。斜率优化要把转移展开为“关于查询量的一次函数”；若用单调队列维护凸包，插入斜率和查询横坐标的单调性都需成立。分治优化需证明最优决策点单调，不能仅因题目有“最小值”就套用。

数论：整除条件先于模意义下的除法

线性筛与欧拉函数

p 存质数，vis 标记合数，phi[1] = 1。每个合数由其最小质因子对应的一次乘法筛掉；遇到整除即停止，是线性复杂度的关键。

int p[N], phi[N], cnt;bool vis[N];void sie(int n) {    phi[1] = 1;    for (int i = 2; i <= n; i++) {        if (!vis[i]) {            p[++cnt] = i;            phi[i] = i - 1;        }        for (int j = 1; j <= cnt && p[j] <= n / i; j++) {            int v = i * p[j];            vis[v] = true;            if (i % p[j] == 0) {                phi[v] = phi[i] * p[j];                break;            }            phi[v] = phi[i] * (p[j] - 1);        }    }}

一次筛表的时间与空间均为 O(n)。大于一的整数可唯一分解为质数幂之积，不计因子顺序；试除一个质因子时要除尽，循环后剩余的大于一部分也要计入。分解 m 后，按每个不同质因子 q，将欧拉函数答案依次改为 ans / q * (q - 1)。欧拉定理 a^φ(m)≡1(modm) 要求互质；非互质时不能随意把指数对 φ(m) 取模。例如模 8 时，2¹ 与 2⁵ 不同。

质数模数 p 下，费马小定理给出非零元素的逆元 a^p−2；威尔逊定理为 (p−1)!≡−1(modp)。后者不意味着用 O(p) 求阶乘就是高效的素性测试。

快速幂、裴蜀与扩欧

下列模幂要求 b≥0、1≤p≤2×10⁹，使余数乘积落在 ll 内。扩欧要求参数非负且不全为零，其系数运算也要在类型范围内。

ll qpw(ll a, ll b, ll p) {    ll s = 1 % p;    a = (a % p + p) % p;    while (b > 0) {        if (b & 1) {            s = s * a % p;        }        a = a * a % p;        b >>= 1;    }    return s;}ll exg(ll a, ll b, ll &x, ll &y) {    if (b == 0) {        x = 1;        y = 0;        return a;    }    ll d = exg(b, a % b, y, x);    y -= a / b * x;    return d;}

裴蜀定理说明 ax+my=c 有整数解当且仅当 gcd(a,m)∣c，这也就是线性同余 ax≡c(modm) 的有解条件。扩欧先求出右侧为最大公约数时的一组系数，再乘 c/d，解的模数为 m/d。逆元存在当且仅当 d=1；合数模数也可能有逆元，关键是互质。

中国剩余定理与非互质合并

已有 x≡a(modm)，加入 x≡b(modn)。写成 x=a+mt，就得到 mt≡b−a(modn)。下面原地更新 a,m，初始各余数已归一化、模数为正，所有中间乘法与合并后的模数均须能用 ll 表示。

bool crt(ll &a, ll &m, ll b, ll n) {    ll x, y;    ll d = exg(m, n, x, y);    ll c = b - a;    if (c % d != 0) {        return false;    }    ll k = n / d;    ll t = c / d * x % k;    if (t < 0) {        t += k;    }    a += m * t;    m *= k;    a %= m;    return true;}

新模数是最小公倍数，不是直接相乘。合并 x≡1(mod4) 与 x≡3(mod6) 得到 x≡9(mod12)；若第二式余数改为 2，差值不能被最大公约数 2 整除，无解。单次合并做一次扩欧；大模数还需安全模乘或更宽的中间类型。

组合计数：先区分对象是否可辨

对互不相同元素，排列数为 n!/(n−r)!，组合数为 (nr)；有重复元素的全排列为 n!/∏c_i!。从 n 类物品中允许重复地选 r 件、只看各类数量，答案为 (n+r−1r)，不是普通组合数。n 个互异元素按旋转视为相同的圆排列为 (n−1)!；是否再把翻转视为相同，需要另行判断对称关系。

质数模数下用阶乘和逆阶乘求组合数，要求预处理上限小于模数；超过模数时阶乘可能为零，不能继续取逆。二项式定理提供 ∑_k(nk)x^ky^n−k=(x+y)ⁿ，鸽巢原理则常用于证明重复、余数碰撞或下界，不是直接代入一个计数公式。

错排列满足 D₀=1,D₁=0、D_n=(n−1)(D_n−1+D_n−2)：先确定一个元素的去处，再按它与目标元素是否互换分两类。卡特兰数可写成

C_n=(2nn)−(2nn−1)。

它统计前缀左括号数不小于右括号数的合法括号序列；用反射将首次越界的路径对应到第二项。模意义下使用差式可避免直接除以 n+1，但求组合数本身仍需满足算法前提。

容斥把所有限制同时满足的数量写成 ∑_S(−1)^|S|F(S)，其中 F(S) 统计至少违反集合 S 中全部限制的对象。求若干集合的并时，改为只枚举非空集合、符号取 (−1)^|S|+1。统计同时被若干数整除，用最小公倍数而非乘积；最小公倍数已超过上界时，贡献为零，及早终止也能避免溢出。