Tricks

2025-02-26T18:14:00+08:00 | 5 分钟阅读 | 更新于 2026-02-27T22:18:55+08:00 | 0 次阅读

@ Jason Chan

高中班主任头像（

[置顶] 3

1. $\min(x,y)=\dfrac{x+y-|x-y|}{2}$

$\max(x,y)=\dfrac{x+y+|x-y|}{2}$ $\min(x,y)+\max(x,y)=x+y$ $\max(|x_i-x_j|,|y_i-y_j|)=\frac12(|x_i+y_i-x_j-y_j|+|x_i-y_i-x_j+y_j|)$.

应用：QOJ 9902 给出 $a_i,b_i$, 求 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}\min(|a_i-a_j|,|b_i-b_j|)$.

Solution

注意到 $\min(x,y)+\max(x,y)=x+y$, 于是所求即为 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}(|a_i-a_j|+|b_i-b_j|-\max\{|a_i-a_j|,|b_i-b_j|\})$.

又由于 $\max(|x_i-x_j|,|y_i-y_j|)=\frac12(|x_i+y_i-x_j-y_j|+|x_i-y_i-x_j+y_j|)$, 故所求为 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}(|a_i-a_j|+|b_i-b_j|-\frac12[|(a_i+b_i)-(a_j+b_j)|+|(a_i-b_i)-(a_j-b_j)|)]$.

于是当前问题的瓶颈在于如何快速求 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}|a_i-a_j|$.

将 $a_i$ 升序排序得到序列 $a_i’$, 则上式等价于 $2\sum\limits^n_{i=1}\sum\limits^{i-1}_{j=1}(a’_i-a’_j)$.

其中 $a’_i$ 被加了 $i-1$ 次, 被减了 $n-i$ 次, 故增加了 $(i-1)-(n-i)=2i-n-1$ 次 $a’_i$.

于是 $\sum\limits^n_{i=1}\sum\limits^n_{j=1}|a_i-a_j|=\sum\limits^n_{i=1}(2i-n-1)a_i’$.

时间复杂度 $\mathcal O(n\log n)$.

第四个等式的证明(参考于OI Wiki ): 实际上是 Manhattan 距离与 Chebyshev 距离之间的转换. 定义 $n$ 维空间中, 点 $(a_1,a_2,\cdots,a_n)$ 与点 $(b_1,b_2,\cdots,b_n)$ 的 Manhattan 距离为 $\sum\limits_{i=1}^n|a_i-b_i|$, Chebyshev 距离为 $\max{|a_i-b_i|}$.

我们在此仅考虑二维空间, 下证明转换的正确性. 将 $A$, $B$ 两点的 Manhattan 距离记作 $d_M(A,B)$, Chebyshev 距离记作 $d_C(A,B)$. 先给一个显然的不等式: $|a|+|b|\ge|a+b|\Rightarrow|a+b|=\max(|a-b|,|a+b|)=\max{\max(a-b,b-a),\max(a+b,-a-b)}$ $$\begin{aligned}d_M(A,B)&=|a_1-b_1|+|a_2-b_2|\&=\max{a_1-b_1+a_2-b_2,a_1-b_1-a_2+b_2,b1-a_1+a_2-b_2,b_1-a_1-a_2+b_2}\&=\max{\max[(a_1+a_2)-(b_1+b_2),(b_1+b_2)-(a_1+a_2)],\max[(a_1-a_2)-(b_1-b_2),(b_1-b_2)-(a_1-a_2)]}\&=\max{|(a_1+a_2)-(b_1+b_2)|,|(a_1-a_2)-(b_1-b_2)|}\&=d_C[(a_1+a_2,b_1+b_2),(a_1-a_2,b_1-b_2)]\end{aligned}$$

故将点 $(x,y)$ 转化为 $(x+y,x-y)$ 即为新坐标系下的 Chebyshev 距离等于原坐标系下的 Manhattan 距离. 同理, $(x,y)$ 转化为 $(\dfrac{x+y}2,\dfrac{x-y}2)$, 新坐标系下的 Manhattan 距离等于原坐标系下的 Chebyshev 距离. Manhattan 坐标系是由 Chebyshev 坐标系旋转 45° 后缩小到一半得到的.

2. 合法括号串问题：

求修改一段串使其变为合法括号串的最小修改次数。设 $f(x)=\begin{cases}-1,&x=\texttt (\1,& x=\texttt)\end{cases}$，$pre$ 为 前缀最大值，$suf$ 为 后缀最小值，则答案为 $\lceil\dfrac{pre}2\rceil+\lceil\dfrac{-suf}2\rceil$.

Proof 我们把所有已经匹配的括号删除，则剩下的串形如 ))))...((.. 设右括号的数量为 $x$，左括号的数量为 $y$ 由于删除的串的贡献对于 $pre$ 与 $suf$ 来说必然是 $0$，那么 $pre=x$，$suf=-y$ 我们尝试设计一种方案来使其操作数最小不妨考虑右括号。对于长度为 $x$ 的连续右括号来说，我们只需要将左侧 $\lfloor\dfrac{x}2\rfloor$ 变为右括号，就可以完全匹配。如果为奇数个，那么由于有解性，右侧的左括号必然为奇数个。这样只需要再多变换一个，即可完全匹配。因此对于右括号而言，答案为 $\lceil\dfrac{x}2\rceil$ 综上，答案为 $\lceil\dfrac{x}2\rceil+\lceil\dfrac{y}2\rceil=\lceil\dfrac{pre}2\rceil+\lceil\dfrac{-suf}2\rceil$

应用：[HNOI2011] 括号修复 / [JSOI2011] 括号序列

3. 不定方程是否有解

裴蜀定理：对于不定方程 $a_1x_1+a_2x_2+\cdots+a_nx_n=v\ \ (a_i,x_i,v\in\mathbf{Z})$，有解当且仅当 $\gcd(a_1,a_2,\cdots,a_n)|v$。

4. 标记永久化

P4092 [HEOI2016/TJOI2016] 树很好的一道示例，不仅将树剖省去为 dfs 序，且又将树剖的 $\log^2n$ 级操作复杂度降为 $\log n$。

由于一段子树的 dfs 序是连续的，因此给某个点打标记时，直接修改这个点所有子树即可，这些点的 dfs 序映射区间也就是 $[id(u),id(u)+sz(u)-1]$。如果当前区间的标记深度小于新标记点，就修改。

查询时，每次分一半往下查，顺便记录最深标记，到了查询点比较返回即可。不理解就画个图模拟一下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int query (int x, int l, int r, int id, int p = 1) {
    if (l == r) return t[x] ? t[x] : p;
    int mid = l + r >> 1;
    if (t[x]) p = t[x];
    if (id <= mid) return query (x << 1, l, mid, id, p);
    else           return query (x << 1 | 1, mid + 1, r, id, p);
}

void modify (int x, int l, int r, int L, int R, int p) {
    if (l >= L && r <= R) {
        if (dep[ t[x] ] < dep[p]) t[x] = p;
        return ;
    }

    int mid = l + r >> 1;
    if (L <= mid) modify (x << 1, l, mid, L, R, p);
    if (R > mid)  modify (x << 1 | 1, mid + 1, r, L, R, p);
}

5. 树状数组+二分维护 MEX 及其扩展

https://www.luogu.com.cn/article/lxczg7kh

6. 线段树维护连续段最值

https://www.luogu.com.cn/problem/P4513 https://www.luogu.com.cn/article/ou0l9p12

7. 最大化 Manhattan 距离

问题 1：给出长度为 $2n$ 的序列 $a_i$，将 $1~n$ 等分成 $p_i,q_i$，最大化 $\sum\limits_{i=1}^{\frac n2}|a_{p_i}-a_{q_i}|$。

假设 $a_i>a_j$，那么 $|a_i-a_j|=a_i-a_j$，所求即为 $\sum a_{b_i}-\sum a_{c_i}$。我们只需最大化前者，最小化后者即可。也就是使第 $1\sim\dfrac n2$ 小做后者，$1\sim\dfrac n2$ 大为前者。

问题 2：给出 $2n$ 个点 $(x_i,y_i)$，将 $1~n$ 等分成 $p_i,q_i$，最大化 $\sum\limits_{i=1}^{\frac n2}|x_{p_i}-x_{q_i}|+|y_{p_i}-y_{q_i}|$。

与一维情况同理。我们设状态：$(1/0,1/0)$ 表示 $x/y$ 是否为前 $\dfrac n2$ 小。$(0,0)$ 与 $(1,1)$ 配对，$(0,1)$ 与 $(1,0)$ 配对即可。

8. 维护信息点到边

如：不能走上一条走过的边。我们可以将信息改成维护边的信息。见初等图论 2.3 。

9. 多起点终点最短路

可建“超级源点”。设起点集合为 $S_0$，终点集合为 $S_1$。取 $s$，$e$，连 $s\to u\quad (u\in S_0)$，$u\to e\quad (u\in S_1)$，求单源最短路即可。

P5304 [GXOI/GZOI2019] 旅行者

显然不同的点之间二进制位至少有一位不同。因此枚举每个二进制位，每个位跑一次最短路，复杂度 $\mathcal O(Tn\log^2n)$。

10. 二分求中位数

把 $>x$ 的作为 $1$，$<x$ 的作为 $-1$。求和，于是可以二分来做。 P2839 [国家集训队] middle

11. 图内奇偶环判断

黑白染色法。

12. 树上最小点覆盖

一个点可以管辖 $k$ 长度的区域，选最少点使每个点都被覆盖。贪心，按照深度从大到小排序，若当前点不被其他点管辖，就选其 $k$ 级祖先。时间复杂度 $\mathcal O(nk)$。见 P2279 这是 $k=2$

13. 树形 dp Trick

可以不维护答案，维护当前子树内边/点之类对答案的贡献。 P3177

14. 计数顺序钦定

钦定一个计数顺序，例如钦定最大值并钦定编号顺序，保证不会重复。 CF486D Vaild Sets

15. 轻重链剖分重儿子判断

对于以 $rt$ 为根的子树，$u$ 不是重儿子的一个必要条件：$sz_u\le \dfrac {siz_{rt}}2$。

这可以在某些问题中把运算次数降低到 $\log n$。

例题见 P5773 [JSOI2016] 轻重路径

16. 一类贡献问题的贪心转化

假设我们要求 $\sum\limits_{i\in A}f(x)-\sum\limits_{i\in \bar A}g(x)$，可以转化为 $\sum\limits_{i\in U}f(x)-\sum\limits_{i\in \bar A}[g(x)+f(x)]$。其中 $U$ 是全集。

CF2140D

17. 维护「不交线段」的一类方法。

Source

From ChatGPT

下面我用中文把题解里提到的四种做法逐一讲清楚：思路、为什么正确、如何实现（要点）、复杂度与一些注意事项。先说明一个统一约定：把圆从点 `1` 和 `N` 之间“切开并展开”成线段 `1,2,...,N`，那么画一条圆弧（弦）连 `A` 和 `B` 可以视为放一个区间 `[A,B]`（保证我们把较小的编号放在左端，使得 `A

方法一：线段树（维护包含点的最短区间）

核心思想： 若已有若干不交叉的区间，考察要插入的区间 [A,B] 是否会与它们交叉。注意：所有包含点 A 的已画区间，因为彼此不交叉，它们的右端点是单调的——最短（右端最小）的那个决定了是否也包含 B。更具体地：

假设已画的包含 A 的区间按长度（或右端）从大到小列为 I1,...,Ik，那么它们的左端依次增大、右端依次减小，且 Ik（最短的包含 A 的区间）是“最靠近 A”的包围区间。如果 Ik 也包含 B，那么所有包含 A 的区间都包含 B；否则存在某个包含 A 但不包含 B 的区间，说明 [A,B] 与之交叉，不能插入。

因此要做两件事：

查询：给定点 x（为 A 或 B），找到当前已插入区间中包含 x 的最短区间（即右端最小的那一个，或等价的某种优先级结构）。
更新：当插入 [A,B] 时，需要把这个区间信息记录到数据结构里，供后续查询使用。

实现要点（用线段树/区间树实现）：可以用一个「区间覆盖的线段树（dual segment tree）」或类似的结构：对于每次插入 [L,R]，把值（例如右端 R）写入到叶子/区间上表示“有一个区间以这个右端覆盖这些左端位置”。查询某点 x 时，取出该位置上当前记录的最小右端（或空表示没有包含它的区间）。具体实现有多种变体，关键是支持：

点查询（取包含该点的最短区间信息） — O(log N)
区间写入（把 [L,R] 这个区间的“信息”写到 L..R-1 或 L 点上，视实现而定）— O(log N)（可用懒标记或覆盖写入）

复杂度： 每次插入/查询 O(log N)，总 O(Q log N)。空间 O(N) 或 O(4N)。

优点/缺点： 常规、确定性；实现相对复杂，需要仔细设计如何把“最短包含”这一选择写入并在查询时得到正确的最小右端。

方法二：把区间看成括号序列（区间转化为括号，维护前缀最小值）

核心思想： 把每个插入的区间 [L,R] 看作在位置 L 放一个 '('，在位置 R 放一个 ')'。若已有的插入区间彼此不交叉，那么在任意一个合法的区间 [A,B] 内，已放的括号序列必须仍然是局部合法的括号序列（即在该区间内，( 与 ) 匹配且最终栈为 0）。相反，如果 [A,B] 要与某个已插区间交叉，那么在 [A,B] 里看 (/) 会出现不合法的情况（例如前缀和出现负值或最终和不为 0）。

把 '(' 替换为 +1， ')' 替换为 −1，则区间 [A,B] 合法当且仅当：

在 [A,B] 范围内，整体和为 0（即 sum_{i=A}^{B} val[i] == 0），并且
在以左端 A 为起点的前缀和中最小值不小于 0（等价于区间内部没有前缀和跌破起点）。

实现要点（线段树支持区间求和与区间最小前缀）： 建立线段树维护每个区间两项信息：

区间和 sum
区间内的最小前缀和 minPref（相对于区间起点的前缀最小）

当需要判断 [A,B] 是否可以插入：

查询区间 [A,B] 的 sum，需为 0；
查询该区间的 minPref，需为 0（即从区间起点到任意位置的前缀和最小值 ≥ 0；因为区间外的历史不会影响区间内部的匹配性，细节上要注意坐标和组合方式）。

插入时，只需把 val[L] += 1 和 val[R] += -1（其实是先在 L 处加1，在 R 处加 -1），在线段树上以点更新维护上述两量。

复杂度： 每次区间查询/两次点更新 O(log N)，总 O(Q log N)。

优点/缺点： 概念直观，把区间问题转为括号合法性；实现上需要线段树支持合并区间的 sum 和 minPref，是标准操作，比较稳健。

方法三：线段树维护按端点分组的最小值（两个最小值）

核心思想： 写法上更偏工程实现的另一种线段树思路。记已有区间为 [L,R] 集合。[A,B] 与某已存在区间交叉的等价条件可以写作两类情况之一存在：

存在 [L,R] 使得 L < A ≤ R < B（即某区间从左边开始包住 A，但右端落在 A 和 B 之间）；
或者存在 [L,R] 使得 A ≤ L < B < R（对称情况）。

要判定是否存在这样的区间，我们可以用线段树在区间端点上维护两类信息（节点代表一个端点区间 [l,r)）：

对于当前节点范围内所有以 右端 R 属于 [l,r) 的已插区间，维护它们的 最小左端 minL_byR（即在该节点范围中，右端落在这里的区间，哪一个左端最小）。
对于当前节点范围内所有以 左端 L 属于 [l,r) 的已插区间，维护它们的 最小右端 minR_byL（即在该节点范围中，左端落在这里的区间，哪一个右端最小）。

利用这两个量可以分别回答上述两类存在性：

要判断是否存在 L < A ≤ R < B：在查询 R 属于区间 (A, B-1] 的节点上（也就是右端 R 在 (A,B) 内），检查这些区间的 minL_byR 是否 < A。如果存在某个右端落在 (A,B) 的已插区间，其最小左端小于 A，则满足第一种交叉。
对第二类类似，查询 L 属于 [A, B-1] 的节点上，检查 minR_byL 是否 > B（或 ≥ B+1，注意端点闭开原则）——即存在左端在 [A,B) 的区间其右端超出 B。

在实现上，节点存两个值，合并时取最小（对于 minL_byR）或最小（对于 minR_byL）等，查询时在合适的索引范围上查询并比较阈值。

复杂度： 每次插入做两次查询 + 更新两端点（把某个区间记入相应的叶或区间）——总 O(log N) 每次，整体 O(Q log N)。

优点/缺点： 这一方法比较“直观地”把两类交叉情况拆开处理，适合写成可复用的线段树节点结构，但实现细节（边界、开闭区间）要小心。

方法四：哈希（随机化）解法 — 用 XOR/随机值判断交叉

核心思想（概率法）： 观察到：两个区间 I 与 J 交叉的一个等价判定是：I 内包含 J 的端点的个数是奇数（或等价：I 包含 J 的端点数为 1），也可从对称角度判断。更一般地，如果对每个点赋一个值 w[pos]（每条线段的两个端点被赋同样的随机值），那么区间 I 内 XOR（或求和 mod 2^B）所有点所对应的 w 值，如果等于 0，则表示该区间内包含的“线段的端点集合”在哈希下合为 0，进而可以用它来判定是否有交叉（具体细节：需要安排好每条线段两个端点值相同，这样被完整包含的区间会贡献两次相同的值 XOR 后为 0；而正好包含一个端点的交叉会导致 XOR 非 0）。因此：

给每一条可能的“线段标识”分配一个随机长整数（通常 64-bit 或更高），并把该随机值写在它的两个端点上（即这两个点的权值 XOR 上该随机值）。
当要判断 [A,B] 是否交叉任一已存在线段时，计算区间 [A,B] 内所有点的 XOR 值；如果 XOR 为 0 则认为不交叉（合法），否则交叉（不合法）。
因为随机值有可能出现哈希碰撞（不同的端点组合恰好 XOR 为 0），这是一种 Monte Carlo 算法：错误概率 ≤ Q / 2^B（用 B-bit 随机值时），取 B=64 概率已经非常非常低。

实现要点：

维护一个支持区间 XOR（或区间和）与点更新的线段树 / Fenwick 树：每次插入 [L,R]，在点 L 与 R 分别 XOR 上该线段的随机值（或者把该随机值加到这两个点上——注意用 XOR 还是加法时要让运算满足“成对抵消”属性；XOR 更简单直观）。
判断 [A,B] 时，计算区间内 XOR，若为 0 则“认为”不交叉并允许插入（同时执行上面的点更新）；否则认为交叉并拒绝插入。

复杂度： 每次点更新/区间查询 O(log N)，总 O(Q log N)。空间 O(N)。

优点/缺点：

实现简单、短代码（Fenwick/树状数组即可做点更新 + 区间前缀XOR）。
但是随机化算法，有极小概率出错；若需要确定性答案，应选前面三种中的任意一种确定性方法。通常使用 64-bit 随机数即可使错误概率可忽略。

附加说明与实现建议

坐标处理：题目给的是圆，上述方法都建立在“把圆切开并展开”这一操作上。要注意把弧对应为区间时的方向统一（例如总把 min(A,B) 作为左端），并保证不会把一个跨越切口的弧误处理为 [B,A]（实现简化的常见做法是先把输入的两个端点按大小排序，如果视为 [A,B]；题目保证所有端点互不相同，且可以选择切口位置来避免跨越问题）。
复杂度：四种方法时间复杂度都是 O(Q log N)（线段树/树状数组的基本复杂度），空间 O(N)。
实际选择建议：
- 想要最稳妥且常见的做法：方法二（括号 + 线段树），概念清晰，线段树求 sum 与 minPref 是经典题型；
- 想要代码简洁且能接受极小概率错误：方法四（哈希 + Fenwick）最快实现；
- 如果擅长写区间覆盖的懒线段树或想直接维护“包含点的最短区间”：方法一可行但实现较细致；
- 方法三是另一种更工程化的线段树拆分两类条件的方法，便于直接检查交叉的两类情形。

18. “車”的放置

在 $n\times m$ 的棋盘中，放置 $k$ 个“車”，使他们互不攻击的方案数为： $$\dbinom nk\dbinom mkk!$$

考虑在 $n$ 行中选 $k$ 个数，再在 $n$ 列中选 $k$ 个数。然后再任意搭配，方案数如上。

https://www.luogu.com.cn/problem/P6453

19. 有序可放置的集合越来越小的计数技巧

我们可以从放置集合小的往大的数处理，如果有序就相当于在已放置的元素中插入，无序是 $i$ 可加入集合看待。

20. 01 串转为 $\le k$ 与 $>k$ 进行计数

见此题解。

21. 若 $x<y<z$，则 $x\oplus z\ge\min (x\oplus y,y\oplus z)$

设 $x$ 与 $z$ 在二进制下最高不同位为 $k$，则 $x\oplus z\ge 2^k$，显然是 $z$ 第 $k$ 位为 $1$。接下来对 $y$ 的第 $k$ 位分类讨论。若 $(y_k)_2=0$，则 $x\oplus y<2^k\le x\oplus z$，反之 $y\oplus z<2^k\le x\oplus z$。

22. 欧拉序+类异或操作 ==> 树上路径修改（树上莫队）。dfs 序 ==> 子树修改。

23. 有关「撤销数据结构」撤销时的顺序

要倒叙，即从最后一个撤销元素开始撤销。见 P5227 的部分。

24. 有关 dfs 序的些许性质

一个点集的 LCA 相当于最大 dfs 序与最小 dfs 序的 LCA

找一个点满足某些性质的最浅 LCA，就相当于找满足这个性质的最大 dfs 序和最小 dfs 分别与这个点的 LCA 的更浅者。

设访问到 $u$ 的时间戳为 $L_u$，访问完 $u$ 子树的时间戳为 $R_u$，则有充要条件：$v\in\operatorname{subtree}(u)\iff L_v\ge L_u\land R_v\le L_u$。
若 $w$ 为 $u,v$ 的公共祖先，那么等价于 $\min(L_u,L_v)\le L_w\land R_w\ge \max (R_u,R_v)$。那么，对于已经是 $u,v$ 之一父节点的 $w$，满足上述命题的否命题，就一定在 $u,v$ 的路径上。
若 $(x,y)$ 路径包含于 $(u,v)$，可以转化为二维数点问题，设 $L_u\le L_v$，$L_x\le L_y$，一条路径 $u\to v$ 的点对为 $(L_u,L_v)$。现讨论：
- 若 $(x,y)$ 路径为一条链。首先限定 $v$ 在 $y$ 子树中，即 $L_v\in[L_y,R_y]$。在此前提下，需要满足二者 LCA 深度不低于 $x$。换句话说，找到 $x\to y$ 路径上的 $x$ 的直接儿子 $z$，$u$ 只要不在 $z$ 的子树内即可。二维平面上 $[1,L_z-1]\times[L_y,R_y]$ 以及 $ [L_y,R_y]\times[R_z+1,n]$ 两个矩形内的点（后面翻转是由于已经限定了 $L_u\le L_v$，防止漏记。
- 若 $(x,y)$ 路径不是链。若 $(u,v)$ 包含 $(x,y)$，那么两对点的 $\operatorname{LCA}$ 必然相同，因此只需使 $L_u\in[L_x,R_x]\land L_v\in[L_y,R_y]$ 即可。体现在二维平面上，已知 $x,y$ 的情况下，查询的是 $[L_x,R_x]\times[L_y,R_y]$ 单个矩形内的点。
树链并。对一组点 $p_1,p_2,\cdots,p_k$ 到根的并统一操作，相当于按照 dfs 序排序后，对 $i\in[1,k]$ 进行链修改（这里是到根进行 $+1$），对 $i\in[1,k)$ 的 $\operatorname{lca}(p_i,p_{i+1})$ 进行链修改（这里是到根进行 $-1$）。我们需要单点查链修改，于是可以用树上差分直接转化，变成子树查单点改，BIT 维护即可。见 P5840。

P3242 [HNOI2015] 接水果

25. lcm/gcd 的一种转化

$\operatorname{lcm}(S)=\prod\limits_{\emptyset\subseteq T\subseteq S} \gcd(T)^{(-1)^{\vert T\vert -1}}$

考虑集合 $S$ 内数的一个质因子 $p$，设 $\min/\max_p(T)$ 表示 $p$ 的最低/高幂，根据 min-max 反演，有： $$p^{\max(S)}=p^{\sum\limits_{T\subset S}(-1)^{\vert T\vert +1}\min(T)}=\prod\limits_{T\subset S}p^{\min (T)\cdot(-1)^{\vert T\vert +1}}$$

设 $P$ 为 $S$ 中所有质因子组成集合，有： $$\operatorname{lcm}(S)=\prod\limits_{p\in P}p^{\max(S)}=\prod\limits_{p\in P}\prod\limits_{T\subset S}p^{\min (T)\cdot(-1)^{\vert T\vert +1}}=\prod\limits_{T\subset S}(\prod\limits_{p\in P}p^{\min (T)})^{(-1)^{\vert T\vert -1}}=\prod\limits_{T\subset S}\gcd(T)^{(-1)^{\vert T\vert -1}}$$

应用：https://atcoder.jp/contests/arc202/tasks/arc202_c

26. 计数转期望

Inversion Sum ，注意到实际上可以枚举每对 $(i,j)$ 并计算成为逆序对的概率，最终乘上 $2^Q$ 即可。

27. 最少交换次数定理

给定长度为 $n$ 的排列 $P$，可以交换任意两个位置的元素。使得 $P_i=i$ 的最小交换次数为 $n-c$。其中，$c$ 是排列中置换环的数量。

这里的置换环是在有向图上，连 $i\to P_i$ 后形成的环。显然，当满足任意 $i$ 都有 $P_i=i$ 时，形成 $n$ 个自环。在一个环中任选两点交换可以形成两个环，在不同的两个环中选两个点交换可以形成一个新环。

应用：ABC436E P10547 [THUPC 2024 决赛] 排列游戏

28. 图的「环基」

https://www.luogu.com.cn/article/z2a09fdw/

CF1515G Phoenix and Odometers 。难点在求一个强连通分量中所有环的 $\gcd$。由于 $\gcd(a,b)=\gcd(a-b,b)$，只需在一个强连通分量中，设到根（遍历起始点）的距离为 $d_u$，对于非树边 $u\stackrel{w}{\to} v$，只需加入 $dis_u-dis_v+w$ 即可。对于返祖边显然。对于横叉边，假设二者 LCA 为$z$，那么相当于 $dis(u,z)-dis(v,z)+w$。考虑强连通分量中包含 $(u,v)$ 的环，根据上面的关系就是将 $z\to v$ 这一段替换为 $z\to u \to v$，进而可以作为一对「环基」。
https://www.luogu.com.cn/problem/P4151 。用到了一个性质是 XOR 两次相当于没有 XOR，因此也是这类模型。

29. $\mathcal O(1)$ 查询 LCA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


void dfs (int u) {
    L[u] = ++ tim;
    tour[++ sb] = u;
    pos[u] = sb;
    dep[u] = dep[fa[u]] + 1;
    for (const auto& v : g[u]) 
    if (v != fa[u]) fa[v] = u, dfs (v), tour[++ sb] = u; 
}

int better (int x, int y) {
    if (dep[x] < dep[y]) return x;
    return y;
}

void init () {
    for (int i = 2; i <= sb; i ++) lg2[i] = lg2[i >> 1] + 1;
    for (int i = 1; i <= sb; i ++) st[0][i] = tour[i];
    for (int i = 1; i <= 19; i ++)
        for (int j = 1; j + (1 << i) - 1 <= sb; j ++)
            st[i][j] = better (st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}

30. Raney 引理

对于整数序列 $a_i$，设 $s_i=\sum\limits_{j=1}^i a_i$。若 $s_n=1$，那么在 $a_n$ 的所有循环同构形式中，有且仅有 一种形式 $b_i=a_j,a_{j+1},\dcots$，使得 $b_i$ 的任意前缀和 $>0$。

P6672 [清华集训 2016] 你的生命已如风中残烛

可以将所有牌面 $-1$，于是就是求任意前缀和不小于 $0$ 的排列数。由于有 $m+1$ 张牌，故最后一张牌牌面设为 $0$。但是这样不好计数，把这个东西挪到首位，让他的值为 $1$，发现牌面和就是 $1$ 了，然后就是这种排列的个数，考虑圆排列，共 $(m+1-1)!=m!$。然后第一张牌其实并不特殊，共有 $m-n+1$ 张都行，然后除掉即可。

31. 多起点，单终点，反推贡献系数。

CF1810G The Maximum Prefix

设 $f_{i,j,k}$ 表示前缀 $[1,i]$ 的和等于 $j$，此时的前缀最大值为 $k$ 的概率。复杂度为 $\mathcal O(n^3)$，难以接受。

但是你从后向前求，假设 $[i+1,n]$ 的前缀最大和为 $mx$，那么考虑自然从 $[i+1,n]\to[i,n]$ 就是 $mx\gets \max(mx+a_i,0)$，于是就可以丢到一维度，设 $f_{i,j}$ 表示前缀 $[i,n]$ 的前缀和最大值为 $j$ 的概率，有

$$ \begin{cases} f_{i,\max(j+1,0)}\gets f_{i+1,j}\times p_i \ f_{i,\max(j-1,0)}\gets f_{i+1,j}\times (1-p_i) \end{cases} $$

但是有点痛苦的是，这样的做法只能做 $k=n$ 的部分，否则还是 $\mathcal O(n^3)$。继续考虑，发现对于每个 $k$，初值是 $f_{k+1,0}=1$ 。如果不看初值，只看转移系数，那么从每个 $f_{1,i}$ 转移过来就好，设 $g_{1,h_i}=h_i$，然后向后转移。答案就是 $g_{k,0}$。

32. 选链树上背包转序列背包

P3780 [SDOI2017] 苹果树