Some Simple Tricks

· · 算法·理论

做题遇到的 trick 还是太多了，所以在这里集一下。

你肯定会在其他地方看到别人的 trick 集合，如：

这些都是非常优秀的文章，至少比本文好。

由于我水平有限，本合集也许更适合入门组选手和提高组选手阅读。

序号是按更新顺序列出的，但是我标了个人主观难度，供参考。

每种 trick 我会给出一个总结性的短语作为小标题，然后会在小标题下方具体阐述。

读者可以按需在右侧边栏跳转。

持续更新。

如果你知道该 trick 的一些题但是我没有加入例题或练习，可以私信我提供。

\gdef\exbm#1{\boldsymbol{#1}} \gdef\crd{\color{red}} \gdef\trick#1{\exbm{Trick\ #1}} % 下面的为需要说明的符号 \gdef\upd#1{\stackrel{\text{#1}}{\gets}} \gdef\din{\text{din}} \gdef\dout{\text{dout}} \gdef\route{\rightsquigarrow} \gdef\dedge#1{\stackrel{#1}{\to}} \gdef\uedge#1{\stackrel{#1}{\leftrightarrow}} \gdef\bedge#1#2{\ \mathop{\leftrightarrow}\limits_{#2}^{#1}\ }

若无特殊说明，例题的时空限制是平凡的，可以默认视作 1\sec,512\text{MB}。

下文中部分变量或符号的表示：

1. (★) GCD log

一个数最多做 log 次改变其值的 gcd。

例 1.1 HDU 5869. Different GCD Subarray Query

给定长度为 n 的正整数序列 a，q 次查询，每次查询给定 l,r，求 a_{l\sim r} 的所有子段的互不相同的 gcd 个数。

由于在固定一个 l 时，对于所有 r，互不相同的 \gcd\limits_{i=l}^r\{a_i\} 是 \log V 级别的。于是我们考虑预处理出来这些块，然后把询问离线下来用 BIT 维护处理即可。

时间复杂度 O(n\log n\log V)。

例 1.2 QOJ 9426. Relearn through Review

给定长度为 n 的正整数序列，可以最多一次对某个区间 [l,r] 内的数 a_{l\sim r} 都 +k，最大化 \gcd\{a_i\}。

暴力枚举是 O(n^2) 的。考虑到前缀 gcd 是单调不升的，可以划分成若干个块。而每一块显然只要钦定对块首进行枚举计算即可。由于块数是 \log n 级别的，故时间复杂度 O(n\log^2n)。

练习 1

2. (★☆) 奇（偶）数位反转

当要对 01 String 进行相邻同项操作时，可以考虑对奇（偶）数位取反，转化为相邻异项操作。

例 2-1. Atcoder TKPPC6-2 B. Replace to Order

给定长度为 n 的由 AB 组成的字符串 S,T，对 S 进行任意次操作，每次选择一个子串 AA（BB），将其翻转为 BB（AA）。求从 S 变成 T 的最小操作次数，或报告无解。

考虑翻转偶数位，这样操作就变成了每次交换相邻的 AB（BA）。于是贪心地钦定考虑每个 A 的相对顺序下位置变化即可。时间复杂度 O(n)。

例 2-2. QOJ 9565. Birthday Gift

给定长度为 n 的由 \tt012 构成的字符串，对其进行任意次操作，每次可以将一个 \tt2 改成 \tt0 或 \tt1，或者删去一个子串 \tt00 或 \tt11。最小化操作后字符串的长度。

考虑翻转偶数位，这样第二个操作就变成了删去一个子串 \tt01 或 \tt10。那么最后整个串一定是全 \tt0 或全 \tt1 的形式。

设字符串原来 \tt0,1,2 的个数为 c_0,c_1,c_2。由于删子串的操作不会改变 |c_0-c_1|，因此对 c_2 和 |c_0-c_1| 的大小关系讨论即可。时间复杂度 O(n)。

练习 2

3. (★★) 倍增 Floyd

当钦定路径要经过 \bm k 条边时，由于 Floyd 用到的运算（\bm{min} 和 \exbm +）满足结合律，因此可以矩阵加速，其他满足结合律的递推运算也适用。

例 3-1. Luogu P2886. Cow Relays G

给定 n 个点 m 条边的无向带权图，求从 s 到 t 经过恰好 k 条边的最短路。

首先补充一下 \trick{3} 的具体内容。

将 Floyd 的转移方程改写为 f'_{i,j}=\min\{f'_{i,j},f_{i,k}+f_{k,j}\}，则做 k 遍就相当于经过 k 条边。

于是可以将 f 看做矩阵，使用矩阵快速幂加速。

时间复杂度 O(n^3\log k)。

例 3-2. Luogu P6190. 魔法

给定 n 个点 m 条边的有向带权图，从 1 走到 n，走的过程中可以使用最多 k 次魔法，每次魔法可以将某一次走的边的权值取负（该次走过这条边后恢复），求 1 走到 n 的最短路。

首先 k=0 直接 Floyd。

对于 k=1，我们枚举改变权值的边 (u,v,w)，有转移方程 f_{i,j}=\min\{f_{i,j},f_{i,u}+f_{v,j}-w\}。

而 k>1，先考虑朴素 dp。记 f_{i,j,p} 表示从 i 走到 j 花费 p 次的最短路，有转移方程 f_{i,j,p}=\min\limits_{x+y=p}\{f_{i,k,x}+f_{k,j,y}\}。

直接暴力肯定不行的。

考虑 k=1 的 f，我们跑 p 遍就是 f_{i,j,2^p}，于是直接矩阵快速幂即可。时间复杂度 O(n^3\log k)。

练习 3

4. (★★★) 倍增优化并查集

当对两个区间内的点顺次合并时，由于并查集的合并满足结合律，因此可以类似 st 表地倍增优化连边。

例 4-1. Luogu P3295. 萌萌哒

一个长度为 n 的正整数 S，有 m 个形如 S[l_{i_1}:r_{i_1}]=S[l_{i_2}:r_{i_2}] 的要求，求满足所有要求的互不相同的 S 有多少个。

由于并查集的合并满足结合律，因此考虑将区间 [l,r] 类似 st 表地，拆成 [l,l+2^k-1],[r-2^k+1,r] 两个长度为 2^k 的区间。于是我们可以开 \log n 个并查集，第 j 个就是 \text{fa}_{i,j}，表示区间 [i,i+2^k-1] 的父亲区间。

于是我们可以处理完后从上往下传信息（即继续拆分区间合并）即可。最后传到 \text{fa}_{i,0} 时，记有 c 个不同的父亲，由于第一位不能取 0，答案即为 9\times 10^{c-1}。时间复杂度 O(n\log n\ \alpha(n))。

练习 4

5. (★☆) 图转生成树

当决策、操作或查询在无向图上不好做时，可以考虑在其生成树（森林）上做。

例 5-1. Luogu P4494. 反色游戏

给定 n 个点 m 条边的无向图，节点为黑白两色，每次可以选择任意一条边，将边的两个端点反转颜色。求对于 \forall i\in[1,n]，删去第 i 个点和其相连的总共 d_i 条边后，在所有 2^{m-d_i} 种决策中，可以所有节点变成白色的决策数量。

首先，由于操作不会改变黑色节点奇偶性，故一个连通块内黑色节点个数为奇数就无解。

先考虑不删除点的情况。

直接在图上不太好做，考虑利用 \trick{5}，如果拉出来一棵生成树，就可以再利用 \trick{25}，在树上从叶子节点往上做出唯一的决策。对于每条非树边无论是否决策都是这样的，故只有一个连通块时方案数为 2^{m-n+1}。拓展到 c 个连通块就是 2^{m-n+c}。

接下来有分类讨论和建圆方树两种做法，这边给出分讨的做法。

我们讨论删除的点对答案有无解造成的影响。

时间复杂度 O(n)。

例 5-2. Luogu P11360. 管道

给定 n 点 m 边的图，求每个极大连通子图内的所有桥。

显然正常的 tarjan 没法做了。

我们考虑一个图内的生成树，发现桥一定是没有被非树边覆盖的树边。于是我们只要在生成树上做路径覆盖，未被覆盖的边就是树边，这个树上差分可以做到。

但是空间仍然不够。发现非树边不会构成环——若构成环，那么必然有删去后对我们操作没有影响的边。

于是我们只要 O(n) 条边。时间复杂度 O(m\alpha(n)+n\log n)。

6. (★☆) 图上连边二元组

给定的二元组可以考虑转化为在图上连边。

例 6-1. ABC155 F. Perils in Parallel

有 n 个具有初始位置 a_i 和初始状态 b_i\in\{0,1\} 的电灯，同时有 m 个开关，第 i 个开关可以将所有 a_j\in[l_i,r_i] 的电灯取反。构造一组选定开关的方案，使得最后有 \forall i\in[1,n],b_i=0。

考虑对 b_i 异或差分，这样区间修改就变成了单点修改，最后要求仍旧是一样的。

考虑连无向边 (l_i,r_i)，这样就变成在图上选边，将边的两个端点取反。利用 \trick{5\ \&\ 25}，在其生成森林上从叶子节点往上做即可。时间复杂度 O(n)。

例 6-2. CF1815C. Between

给定正整数 n,m 和 m 个二元组 (a_i,b_i)\ (1\le a_i\neq b_i\le n)，构造一个尽可能长的序列 p，要求满足：

  • 存在恰好一个 p_i=1。
  • 对于 \forall i\in[1,m]，满足对于 \forall x,y\in[1,|p|]\land x<y\land p_x=p_y=a_i，有 \sum\limits_{k=x}^y[p_k=b_i]\ge1。

给出一个尽可能长的构造，或报告序列长度可以无限长。

设 c_i 为 i 出现次数，则对于二元组 (x,y)，有 c_x\le c_y+1。考虑二元组连边 b_i\dedge 1 a_i，bfs 一遍可以得到每个 c_i 的最大值。

然后构造。令 d_i 表示出现次数为 i+1 的数构成的序列。令 s(l,r)=d_r,d_{r-1},\cdots,d_l，那么有构造 s(x,1),1,s(x,1),s(x,2),s(x,3),\cdots,s(x,x)。

时间复杂度 O(nm)。

练习 6

7. (★★★) 图上分治

对于在图上诸如删（留）点、边的操作求某个东西时，可以利用分治避免没有受影响的部分重复计算。

例 7-1. XYD19310. 先驱者

给定 n 个节点的无向带权图，定义 d(p,x,y) 为 x 到 y 途中不经过 p 的最短路（特别地，若 p=x 或 p=y，则为 x 到 y 的最短路；若不存在路径，则定义为 -1）。求 \sum\limits_{p=1}^n\sum\limits_{x=1}^n\sum\limits_{y=1}^nd(p,x,y)。

暴力 Floyd 是 O(n^4) 的，显然跑不过去。

注意到在去掉一个点的时候，有很多没有被影响到的点对 (x,y) 是被重复计算的。

考虑分治，记 \text{sol}(l,r) 表示 p\in [l,r] 时的全源最短路。这样当 l=r 时就可以直接累加答案。钦定一定经过 [l,\text{mid}]，然后跑 k\in[l,\text{mid}] 的 Floyd，进入 \text{sol}(\text{mid}+1,r) 即可（反之亦然）。时间复杂度 O(n^3\log n)。

例 7-2. Luogu P5631. 最小mex生成树

给定 n 个点 m 条权值为 w_i 的边构成的无向连通图。求其生成树构成的边集的 \text{mex} 的最小值。

注意到 w 范围较小，暴力可以考虑枚举答案，加入剩余的边看合法性。时间复杂度 O(wm\cdot\alpha(n))。

注意到在枚举的时候很多东西重复算了，考虑分治。记 \text{sol}(l,r) 表示边权范围在 [l,r] 的不选的答案。那么当 l=r 时如果节点之间连通，那么答案就是 r。钦定选 [l,\text{mid}] 的边，用并查集维护，然后进入 \text{sol}(\text{mid}+1,r)（反之亦然）。由于要回溯，使用可撤销并查集即可。时间复杂度 O(w\log w\log n)。

8. (★) DAG 分层图

对一个 DAG 建的分层图的正（反）图仍然是一个 DAG。

例 8-1. Luogu P3119. Grass Cownoisseur G

给定 n 点 m 边的有向图，最大化从 1 开始走最后回到 1 经过的不同节点数量，中途允许逆向通过某条边最多一次。

首先显然地缩点成 DAG，然后考虑构建分层图。

对于原图的 u\to v，我们在新图中，可以构建 u_1\to v_1\to u_2\to v_2，这样一次逆行后不会出现第二次逆行。

DAG 分层后能否直接 dp 呢？

由于对于每一层都是一个 DAG，并且跨层之后不会回到原来的层，因此它依旧是一个 DAG，可以直接在上面 dp。

时间复杂度 O(n+m)。

9. (☆) 括号串拼接

两个合法括号串拼接时，新串较原来会多出一个子串 )(。

例 9-1. CF1726C. Jatayu's Balanced Bracket Sequence

给定长度为 2n 的合法括号串 S，第 i 个字符可以看作编号为 i 的节点，存在无向边 (x,y) 当且仅当 S[x:y] 是一个合法括号串。求该图连通块个数。

首先对于 \texttt{((...))} 的串，每一对括号之间都是互不影响的。连通块个数会减一当且仅当两个合法括号串拼接产生。而两个合法括号串拼接时中间恰好会多出来一个子串 )(。因此记 S 中 )( 的数量为 c，答案为 n-c。时间复杂度 O(n)。

10. (★) （质）因数虚点连边

当图上路径与点权因数有关时，可以和考虑将该点连向其点权的（质）因数。

例 10-1. CF1775D. Friendly Spiders

给定 n 个点权为 a_i 的节点 i，i 与 j 可以连接边权为 1 的无向边当且仅当 \gcd(a_i,a_j)\neq1。求 s 到 t 的最短路，并给出一个可行路径。

直接 bfs 是会炸的，考虑优化。

我们可以建立质数虚点，将 i 连向 a_i 所有的质因子，然后就可以跑 bfs 了。

时间复杂度 O(n\log n)。

11. (★★★) 单侧递归线段树

线段树区间合并信息不能直接做而需要满足一定关系时，可以考虑递归合并。

例 11-1. Luogu P4198. 楼房重建

在平面的横坐标为 i\in[1,n] 的地方，有线段 (i,0)-(i,H_i)，初始 H_i=0。m 次修改，每次修改一个 H_i，并查询从 (0,0) 最多能看到多少线段。

单侧递归线段树模板。

考虑用线段树维护答案，但是上传信息不好处理。

下面令 \text{maxl}_S 表示区间 S 中最多可看到的楼房数量，\text{maxs}_S 表示区间 S 中的最大斜率。

首先对于区间 [l,r]，其左区间的信息一定是会在这个区间里（由题意可得）。

考虑递归处理右区间的情况，并传入该区间的值所必须要大于的最小值 x。

若中途遇到一些不会对答案产生贡献的情况就不用考虑，直接跳出即可。

时间复杂度 O(n\log^2n)。

12. (★★) 曼哈顿与切比雪夫互化

当坐标系内涉及曼哈顿距离（切比雪夫距离）但是不好做时，可以考虑将坐标系旋转 \textbf{\textit{45\degree}} 转化成切比雪夫距离（曼哈顿距离）。

例 12-1. Luogu P3964. 松鼠聚会

平面上有 n 个点 (x_i,y_i)，选择一个点 (x,y)，最小化 \sum\limits_{i=1}^n\max\{|x-x_i|,|y-y_i|\}。

切比雪夫距离不太好做，考虑转化为曼哈顿距离。

重建坐标系，令 (x',y')=\left(\dfrac{x+y}2,\dfrac{x-y}2\right)，则原坐标系的切比雪夫距离，就是新坐标系的曼哈顿距离。

然后就随便做了。

时间复杂度 O(n\log n)。

例 12-2. Atcoder Code Festival 2017 QualA D. Four Coloring

构造一个 n\times m 的含有 RYGB 四种颜色的网格，使得所有曼哈顿距离恰好为 d 的一对网格颜色互不相同。

1\le n,m\le 500,1\le d\le n+m-2

很容易往黑白染色上想，但是 d 为偶数时似乎没有什么前途。

重建坐标系，令 (x',y')=(x+y,x-y)，则原坐标系的曼哈顿距离，就是新坐标系的切比雪夫距离。

然后可以对每 d\times d 划出来，内部填入一种颜色，外部交替形如下：

\def\red{\color{red}\rule{10px}{10px}} \def\yel{\color{yellow}\rule{10px}{10px}} \def\grn{\color{limegreen}\rule{10px}{10px}} \def\blu{\color{skyblue}\rule{10px}{10px}} \begin{aligned} \red\yel\red\yel\red\yel\red\yel\\[-6.5pt] \blu\grn\blu\grn\blu\grn\blu\grn\\[-6.5pt] \red\yel\red\yel\red\yel\red\yel\\[-6.5pt] \blu\grn\blu\grn\blu\grn\blu\grn\\[-6.5pt] \red\yel\red\yel\red\yel\red\yel\\ \end{aligned}

时间复杂度 O(nm)。

练习 12

13. (★★★) 直方图转笛卡尔树

在一个直方图上操作时，可以考虑将其横向划分成若干个极大的矩形，建立笛卡尔树。

例 13-1. Luogu P6453. PERIODNI

给定一个宽 n 高分别为 a_i 的格点直方图，要求在格子内放入恰好 k 颗棋子，要求任意两颗棋子如果共行（列），棋子之间应当有超过 1 个极长连续段。求放置方案数，对 10^9+7 取模。

考虑一个直方图：

\rule{10px}{10px}\rule{10px}{40px}\rule{10px}{30px}\rule{10px}{50px}\rule{10px}{10px}\rule{10px}{30px}\rule{10px}{20px}

对其进行横向划分：

\def\red{\color{red}} \def\org{\color{orange}} \def\ord{\color{orangered}} \def\yel{\color{gold}} \def\grn{\color{limegreen}} \def\skb{\color{skyblue}} \def\blu{\color{blue}} \def\pur{\color{purple}} \def\pnk{\color{pink}} \def\wht{\color{white}} \def\r#1#2{\rule{#1px}{#2px}} \begin{array}{c} \quad\red\r{10}{10}\quad\ord\r{10}{20}\quad\quad\quad\\[-3.5pt] \quad\org\r{30}{10}\quad\yel\r{10}{10}\quad\\[-3.5pt] \quad\org\r{30}{10}\quad\grn\r{20}{10}\\[-3.5pt] \skb\r{70}{10} \end{array}

从下往上，根据它们的相连关系，可以建出笛卡尔树。

然后考虑 dp。设 f_{x,i} 表示以 x 为根的子树放了 i 颗棋子的方案数，g_{x,i} 表示以 x 为根的子树但不包含 x，放了 j 颗棋子的方案数。记 \text{lson}_x,\text{rson}_x 分别表示 x 的左右儿子，h_x,w_x 分别为节点 x 对应的矩形的高、宽，则有：

g_{x,i}=\sum\limits_{j=0}^if_{\text{lson}_i,j}\cdot f_{\text{rson}_i,i-j}\\ f_{x,i}=\sum\limits_{j=0}^i\binom{h_x}{i-j}\cdot\binom{w_x-j}{i-j}\cdot(i-j)!\cdot g_{x,j}

时间复杂度 O(nk^2+n^2)。

练习 13

14. (★★★★) 耳分解 DP

补充定义和性质：
对于一个（强）连通图 G，其「耳」是一条简单路径（这也被称作「开耳」）或简单环。
一张图是「可耳分解」的，当且仅当可以每次从中删去一个耳，并且最终所有边都被删除。这一过程被称作「耳分解」。

  1. 一张有向图是「可耳分解」的，当且仅当它强连通。
  2. 一张无向图是「可耳分解」的，当且仅当它边双联通。

如果要对于一个图的强连通（边双连通）子图求解，可以考虑对其耳分解。

例 14-1. Luogu P5776. Quare

给定一个 n 点 m 边无向带权图，最大化其边双连通子图的边权和。

考虑用状压 dp 逐渐加入耳。

记 f_{S,i,j} 表示点集 S 加入耳分解，且不完整的那个耳的最后一个节点为 i，该耳最后连向 j 的最小代价。

然后直接做即可。

时间复杂度 O(2^nn^3)。

15. (★★☆) BIT 倍增

当要做二分套 BIT 时，有的时候由于有很多重复计算的部分，因此可以利用其转成一个 BIT 上倍增的过程。

例 15-1. Luogu P6619. 冰火战士

有两个二元组集合 A,B，会进行共 q 次插入和删除二元组 (x,y) 的操作，每次操作完都要钦定一个 k，令 f(k)=\sum\limits_{\substack{(x,y)\in A\\x\le k}}y,g(k)=\sum\limits_{\substack{(x,y)\in B\\x\ge k}}y,w(k)=\min\left(f(k),g(k)\right)，输出 2w_{\max}(k) 和 \max\{k\mid w(k)=w_{\max}(k)\}。

首先一个简单的观察是 w(k) 是一个单峰函数，但是有不变的段，不能三分。

不难想到可以先二分出一个 k_0 满足 f(k_0)<g(k_0),f(k_0+1)\ge g(k_0+1)，再找到 k_1=\max\{k\mid g(k)=g(k_1+1)\}。这样答案必然是 k_0,k_1 中的一个。

这个过程直接二分套 BIT 是 O(q\log^2q) 的，考虑优化。

注意到我们在计算前后缀和时有很多重复使用的段。由于 BIT 的节点 x 存的是 [x-\text{lowbit}(x)+1,x] 的信息，所以按二进制位从高到低枚举，这样倍增就和原来的二分等价了。中间求前缀和的过程我们就直接记一个当前的和，然后累加即可。

时间复杂度 O(q\log q)。

16. (★★) 生成树异或环

一个无向图中的任意环可以用若干个其生成树上非树边 \bm{(u,v)} 及 \bm{u,v} 的树上路径所构成的环进行异或并得到。

例 16-1. Luogu P4151. 最大 XOR 路径

给定 n 点 m 边无向带权（w）连通图，求一条 1\to n 路径（不一定是简单路径），使得异或和最大。

原问题等价于一条 1\to n 的简单路径异或上若干个简单环。因为显然你可以在路径上行走时拐向前往某个环绕一圈再原路走回来，这样中间拐的那一段就异或没了。

上述的简单路径可以是任意的，因为如果有更优路径就可以将其和原有路径构成一个环并异或掉。

根据 \trick{16}，我们可以取原图的任意生成树，将非树边与其覆盖路径构成的环的异或权值扔进线性基，这样只要在线性基上查询最大异或和即可。

时间复杂度 O(n+m\log w)。

例 16-2. CF19E. Fairy

给定 n 点 m 边无向图，求删除一条边后该图变成二分图的所有方案。

**请思考线性做法。**

显然答案是所有奇环的交，但这显然不是很可做。

我们称其覆盖的路径构成的是奇环的非树边为「奇边」，类似地有「偶边」。

根据 \trick{16}，我们注意到任意奇环都可以通过若干个奇边对应的的奇环异或并得到。而且，奇边被加入答案当且仅当只存在这一条奇边。

接下来考虑树边的情况。

若一条树边同时被奇边和偶边覆盖，那么一定不会是答案边。原因是奇边对应的奇环和偶边对应的偶环可以异或得到一个奇环，删去这条树边并没有影响。

也就是说，答案就是恰好被所有奇边覆盖的树边。

容易想到维护路径上的边权：给奇边覆盖的树边 +1，给偶边覆盖的树边 -1，这样边权最终恰好为奇边数量的边就是答案。

如果生成树是 dfs 树，那么非树边就都是返祖边，就可以搜索的时候处理。

时间复杂度 O(n+m)。

练习 16

17. (★★★) 基于决策强制性的 DP 状态

正常的描述决策的 DP 状态为 \bm{f_{i,0/1}} 表示决策 \bm i 选或不选，有时出于一些特殊原因，这样设状态反而不太好做，可以改用 \bm{f_{i,0/1}} 表示决策 \bm i 是否强制选（不选）。

例 17-1. CF808G. Anthem of Berland

给定两个小写字母构成的字符串 s,t，其中 s 还可能有字符 \texttt ?，将每个 \texttt ? 替换为一个任意小写字母后，最大化 t 匹配 s 的次数。

考虑描述一个前缀的后缀是否被 t 匹配，记 f_{i,0/1} 表示 s 的最后 |t| 个字符是否被 t 匹配的最大匹配次数。

这个应该也是好做的，本题先用来感受一下决策强制性的 dp 状态。

考虑换一种 dp 状态含义：f_{i,0/1} 表示 s 的最后 |t| 个字符是否强制被 t 匹配的最大匹配次数。

\gdef\bd{\text{bd}}

记长度为 i 的前缀的 border 长度为 \bd_i。

对于 f_{i,0}，显然有 f_{i,0}=\max\{f_{i-1,0},f_{i,1}\}。

对于 f_{i,1}，我们初始有 f_{i,1}=f_{i-m,0}+1，然后可以容易地转移，有 f_{i,1}\upd{max}\max\limits_{j\in S}\{f_{i-m+j,1}\}+1，其中 S=\{\bd_m,\bd_{\bd_m},\bd_{\bd_{\bd_m}},\cdots\}。

匹配可以直接暴力匹配，时间复杂度 O(|s|\cdot|t|)。

例 17-2. Luogu P8352. 小 N 的独立集

给定一棵 n 个节点的树，每个节点需要钦定一个点权 [1,k]，对于所有 k^n 种不同情况，求最大权独立集为 [1,nk] 的分别有多少种情况。答案对 10^9+7 取模。

首先最朴素的 dp 为 f_{x,0/1} 表示节点 x 的子树，是否选 x 的最大权独立集。时间复杂度 O(nk^n)。

注意到由于 k 非常小，nk 仍然是一个很小的数字，我们考虑 dp of dp，将 f_{x,0/1} 作为状态，设 f_{x,i,j} 表示 x 的子树中 f_{x,0}=i,f_{x,1}=j 的方案数。

枚举 x 的儿子 y，枚举状态 (i,j,p,q)=(f_{x,0},f_{x,1},f_{y,0},f_{y,1}) 对应的答案。那么有转移式 f_{x,i+\max\{p,q\},j}\upd+f_{x,i,j}\cdot f_{y,p,q}。时间复杂度 O(n^4k^4)，并且远达不到。

但这仍然无法解决题目。

我们考虑改变 f_{x,0/1} 的含义：f_{x,0/1} 表示节点 x 的子树，是否强制不选 x 的最大权独立集。

强制不选只会影响节点 x 的差值，故有 0\le f_{x,0}-f_{x,1}\le k。那么可以重新设 f_{x,i,j} 表示 x 的子树中 f_{x,0}=i+j,f_{x,1}=i 的方案数。

同理枚举 x 的儿子 y，枚举状态 (i+j,i,p+q,p)=(f_{x,0},f_{x,1},f_{y,0},f_{y,1}) 对应的答案。那么有转移式 f_{x,i+p+q,\max\{j-q,0\}}\upd+f_{x,i,j}\cdot f_{y,p,q}。

时间复杂度 O(n^2k^4)。

练习 17

18. (★★) 补集转化

限制某一个子集的条件时，可以考虑其补集。

常见的补集转化如：独立集 & 点覆盖。

例 18-1. Luogu P9036. 挑战 NPC Ⅲ

求一个 n 点 m 边的无向图中大小恰好为 n-k 独立集数量。将答案对 998244353 取模。

原问题可以转化为大小恰好为 k 的点覆盖计数。

首先，对于一个度数 >k 的节点，我们必然是会选择的，否则为了覆盖与它相连的边，我们必须把这些边另外的 >k 的点都选中，这就和恰好选 k 个矛盾了。

其次，进一步地，我们这样剩下来所要覆盖的边的条数不超过 k^2，如果超过了，自然就无解。

这样的话，我们就剩下了 O(k^2) 条边。

记 a_i 表示节点 i 被选的状态：

考虑爆搜。记 \text{dfs}(x,r) 表示已经选择了 x 个点加入点覆盖集，还剩下 r 个点没有被确定。

那么，首先找到一条没有被覆盖的边 (u,v)。

最后注意处理重边的情况。

时间复杂度为 O(T(k)k^2)，其中 T(k)=2T(k-1)+T(k-2)，大约为 O(2^kk^2)，跑不满。

此外还有一种做法。

我们继续考虑每个点的度数。

这样就可以做到 T(k)=T(k-1)+T(k-3)。

练习 18

19. (★★) 无向边定向

当在无向图上解决问题时，可以考虑给无向边定向。

19-1. Luogu P1989. 无向图三元环计数

经典题。

定向 u\to v 当且仅当 (\deg_u,u)<(\deg_v,v)。然后枚举点 u，将 u\to v 的 v 打上标记，枚举所有 v\to w，若 w 打上标记则计数。时间复杂度 O(m\sqrt m)。

证明也是容易且经典的。

首先对于一条边 (u_i,v_i)，贡献为 \dout_{v_i}。

故时间复杂度为 O\left(\sum\limits_{i=1}^m\dout_{v_i}\right)=O(m\sqrt m)。

20. (★★★) 有向环求交

求有向环的交时，可以考虑先定一个主环，然后从后往前记录每个点不经过环上的边所能够达到的最远点，两点之间的点必然不合法，最终可以线性求出。

例 20-1. CF982F. The Meeting Place Cannot Be Changed

给定 n 点 m 边无向图，求所有环的交，输出交集中的一个节点即可，无解输出 -1。

首先补充一下 \trick{20} 的具体内容。

我们在图中随便找到一个环，作为主环。如何求交是困难的，考虑把不交的去掉。对于主环上的每个点，记录其不经过环上的边所能够达到的最远点，将两点之间的点标记为不合法。直接做是 O(n^2) 的。

但是注意到一件事情，我们倒着做，对于一个点 u，经过非主环边走到了下一个节点 v，而节点 v 已经搜过了，并且 v 所达到的最远点一定是 u 向 v 走下去所能够达到的，因此无需重复搜索。然后我们断开环差分即可。

但是，非主环边可能有向前走后向后回退的情况，如依次几个点 A\route C\route B\route D\route A，若存在非主环上路径 A\route E\route F\route D，并且有 B\to E,F\to C。这种情况下，显然有环 B\to E\route F\to C\route B，删去这个环上的点，并不能保证同时不存在环 A\route E\route F\route D\route A 和主环 A\route C\route B\route D\route A，因此这种情况无解。

也就是说，我们在选出一个答案点时，事先认为有解，最后判一下答案合法性即可。

时间复杂度 O(n)。

练习 20

21. (★★) 无向环交上限二

对于一个无向图中若存在多于一个简单环，则这些环点集的交的大小不超过二。

我忘记有啥例题了，有知道的可以私我。

22. (★★☆) 序列值域转 01

存在一个阈值 \bm x，要对 \exbm{≤x} 的和 \exbm{>x} 的操作时，可以考虑将 \exbm{≤x} 的变为 \bm 0，\exbm{>x} 的变为 \bm 1。

例 22-1. Luogu P2824. 排序

给定一个 1\sim n 的排列，m 次操作，每次可以对一个下标区间在 [l,r] 的数进行升序（降序）排序，所有操作结束后查询位置 q 上的数。

正常的排序显然是不行的，考虑 \trick{22}，若转化成 01 序列的排序，那么我们可以直接统计 01 个数后区间覆盖。

将操作离线下来，考虑二分答案。假设现在二分的答案为 \text{mid}，那么我们就把 \le\text{mid} 的设为 0，>\text{mid} 的设为 1，然后用线段树维护过程，最终位置 q 的数为 0 就是合法的。

时间复杂度 O(m\log^2n)。

23. (★★) 无向图网络流

无向图可以直接跑网络流。

例 23-1. Luogu P1674. Secret Milking Machine G

给定一张 n 点 m 边的无向带权（w）图，求出 t 条 1 到 n 的路径，并最小化这些路径上权值最大的边。

首先不难想到二分答案。

然后我们考虑网络流建模：设二分的当前答案为 k，利用 \trick{22}，将 \le k 的边权设为 1，>k 的设为 0，这样其实等价于保留所有权值 \le k 的边。然后我们只要判定该图的最大流是否 \ge t 即可。

可这是无向图啊？这怎么跑网络流？

考虑一个有向图，我们建模时是有 u\bedge w0 v，其中 v\dedge0u 是用于回流的。网络流增广的时候不会同时走两个方向，反边用于存储反流，而无向图中的这个反边仍然具有这个作用，因此是可以直接跑最大流的。

时间复杂度 O(nm\log w)。

24. (★) 大小调整取等

假设任意选择某个集合，其权值既可能大于，也可能小于一个给定值，如果可以通过调整将权值 \boldsymbol{\pm 1}，则可以取到等号。

例 24-1. CF1658F Juju and Binary String

给定一个长度为 n 的 \tt01 串，要求取最少的不相交子串，要求：

  • 取出的子串长度和为 m。
  • 这些子串总的 \tt0 个数和总的 \tt1 个数的比值和原串相同。

给出一种可行方案，或报告无解。

设 s 中 \tt 1 的个数为 c_1，则选取的子串的 \tt 1 个数和为 c=\dfrac{c_1m}n，故 n\nmid c_1m 则无解。

考虑 \trick{24}。也就是有一个搞笑的事情是，你在取的过程中一定是 >c 和 <c 的情况都有的，而对于这两种情况，他们中间必然是对 \tt 1 的个数进行 \pm1 的调整，所以一定会出现 =c 的情况。因此答案上界为 2。

时间复杂度 O(n)。

25. (★) 从叶向根

对于树上的操作，可以考虑从叶子节点向上操作。

例 25-1. Luogu P11762. 走亲访友

给定一个 n 点 m 边的无向连通图（无自环、重边），你需要构造一组满足下面要求的路径：

  • 起点为 s，终点不限。
  • 对于走过的每一组边 (u_i,v_i)，你需要额外决定 p_i\in\{0,1\}，满足：
    2. 如果 i>1，那么 u_i=v_{i-1}。即使 p_i=0，也需要满足这条限制。
  • 路径的长度不能超过 k。
  • 最后未删除的边组成一棵 n 个节点的树。

保证存在一个合法的方案。

首先可以容易得到一个上限为 2m 的做法：直接暴力 dfs，搜到一个非树边就返回并清除该边。

这个看起来没什么前途，因为我们的瓶颈在于每条边都要来回走，中间浪费了很多。

但是给了我们启示，发现它是一个欧拉回路。

于是就考虑能否将我们走的路径构成欧拉回路。

但是显然，图中的奇度点较多，如何处理？

考虑 \trick{5} ，将在图上的决策转化为生成树上。然后再利用 \trick{25}，我们可以从叶子开始从下往上给树边加重边。由于一条边会对两个节点的度数贡献，所以最后到根节点的时候根的度数一定是偶数。

然后我们跑欧拉回路即可。

由于每条树边最多被加一次重边，所以最坏路径长度为 2(n-1)+m-(n-1)=m+n-1，恰好在限制范围内。

时间复杂度 O(n+m)。

26. (★★☆) 分块 ST 表

当因为空间、时间等问题 st 表无法直接处理时，可以考虑分块后再上 st 表处理。

例 26-1. Luogu P3793. 由乃救爷爷

给定长度为 n 的正整数序列 a，m 次询问，每次询问给定区间 [l,r]，求 \max\limits_{i=l}^r\{a_i\}。

虽然是四毛子板子，但是可以考虑一个更为简洁的东西，也是官方做法。

普通的 st 表在这里的瓶颈在于空间 O(n\log n) 开不下。

考虑按块长 B 分块，这样一个询问就可以拆成后缀最大值、块间最大值、前缀最大值三个子问题。我们预处理块间 st 表和块内的前后缀最大值即可。

空间复杂度 O\left(\dfrac nB\log\dfrac nB\right)，时间复杂度 O\left(\dfrac nB\log\dfrac nB+q\right)，取 B=\log n 时为 O(n)。

当然，询问会有区间在同一块内的情况。这种情况期望下是 O\left(\dfrac{B^2}n\right) 的。结合上述内容 B 可以取 [\log n,\sqrt n]，对应的期望时间复杂度为 O(n) 到 O(m) 左右。

例 26-2. Luogu P11750. 谢谢您。

给定一个长度为 n 的正整数序列 a，和 m 个区间 [l_i,r_i]。q 次询问 x,y,k，求 \max\limits_{i=x}^y\left\{\sum\limits_{j=l_i}^{r_i}[a_j=k]\right\}。

下面令 m 个给定的区间为「关键区间」，q 个询问的区间为「询问区间」。

看到出现次数，考虑根号分治。设 c_k=\sum\limits_{i=1}^n[a_i=k]。

剩余的工夫就是大力卡常了。

27. (★☆) 操作离线倒序

当操作直接做比较困难时，可以考虑离线下来倒着做。

例 27-1. Luogu P2391. 白雪皑皑

给定长度为 n 的序列 a，初始 a_i=0。m 次操作，每次操作给定区间 [l,r] 和正整数 x，将 a_{l\sim r} 全改为 x。求最后每个位置上的数。

直接维护显然会爆。

由于我们只关心最后的数，所以我们考虑把操作离线下来，倒过来做。

对于一个区间 [l,r]，若答案都未确定，那么 x 就是这些数的最终答案。而此后我们都不需要管这些数了。直接用链表或并查集维护即可。

由于每个数只会访问一次，故时间复杂度为 O(n+m) 或 O(n\log n+m)。

例 27-2. Luogu P11674. Reachable Pairs G

给定 n 点 m 边的无向图，并给定一个长度 n 的 \tt01 串 s，表示进行 n 次操作。对于第 i 次操作，若 s_i=0，则在图中删去点 i；若 s_i=1，则在图中删去点 i 的同时给每个原来与其相连的节点之间两两加边。每次操作后，都查询两两可达的节点对数。

维护删点是不好做的，但是维护加点是更为容易的。考虑离线下来倒着做。

更进一步地，我们将节点黑白染色，黑色代表当前不存在该节点，白色反之。

那我们只需要加边维护连通块内白点数量就可以了。并查集容易做到。时间复杂度 O(n\alpha (n)+m)。

练习 27

28. (★) 权值减下标

对于一些和序列递增相关的东西，可以考虑将权值减去下标。

例 28-1. CF2009G1 Yunli's Subarray Queries (easy version)

给定长度为 n 的正整数序列 a_i 和正整数 k，q 次询问，每次查询一个区间 [l,r]，问使得存在 i\in[l,r-k+1] 有对于 \forall j\in[i,i+k),a_j+1=a_{j+1} 的最少修改次数。

令 a'_i=a_i-i，那么问题等价于使得一个区间存在长度至少为 k 的颜色段的最少操作次数。滑动窗口预处理即可。

时间复杂度 O(n+q)。

例 28-2. Luogu P11833. 推箱子

数轴上给定 n 个依次排列的箱子，每个单位时间内可以移动一个箱子一个单位长度，而第 i 个箱子要在开始移动后的 t_i 个单位时间内从初始的 a_i 移动到 b_i，问能否达成要求。T 组数据。

首先有一个显然的贪心是按 t_i 升序做。

考虑维护这样的过程。对于正在移动的第 i 个箱子，当前位置到目标位置 b_i 间必然有很多箱子，我们当然选择尽量少的移动它们——即将需要移动的箱子区间 [l,r] 位置变为 b_i,b_i+1,b_i+2,\cdots。找到这个右界，我们可以线段树二分，而修改我们自然可以修改为等差数列，线段树标记即可。

当然，为了更加简便，可以将 a_i,b_i\upd{--}i，这样就可以直接用线段树区间覆盖，更为简便。

时间复杂度 O(Tn\log n)。

29. (★★★★) 值域随机映射

遇到一些和值域关系不大的题时可以考虑将值域随机重新映射。

例 29-1. CF1746F. Kazaee

给定长度为 n 的序列 a，m 次操作，每次操作可以单点修改，或给定区间 [l,r] 查询是否对于 \forall k\in[l,r],\ k\left|\sum\limits_{i=l}^r[a_i=a_k]\right.。

这个东西看着就很带修莫队，但是并不太能做。

考虑查询操作所满足的要求。将这个条件弱化，也就是变成一个必要不充分条件，有 k\left|\sum\limits_{i=l}^ra_i\right.，因为考虑对于每个数 i，其贡献了出现次数 c_i 次，即 \sum i\cdot c_i，由于 k\mid c_i，所以 k\left|\sum\limits_{i=l}^ra_i\right. 一定满足。

显然直接判这个条件是只会有错误判为正确的情况的。这种情况的原因在于会出现 k\mid i,k\nmid c_i 的情况。注意到值本身对我们来说没有任何作用。利用 \trick{29}，将每个数 x 重新映射到一个值域内的另一个数 y。原先错误的概率为 \dfrac1k，假设重新映射 x 次，那么概率就是 \dfrac1{k^x}，非常小。考虑最坏 k=2，所以取 x=\log V\approx30 就足够了。

时间复杂度 O(n\log^2n)。

30. (★★★) 分部分做法

一些问题直接用某种做法并不好做，但是在一定次数的某种做法后会满足某些性质，并使用另一种做法。

例 30-1. CF1704E. Count Seconds

给定 n 点 m 边的 DAG，点 i 初始有点权 a_i。每个单位时刻内，会首先令 S=\{i\mid a_i>0\}，然后对于每个 x\in S，a_x\upd{--}1，接着对于 \forall(x,y)\in E,a_y\upd+1。求出所有 a_i=0 的最早时刻，答案对 998244353 取模。

一个直接的想法是 dp，设 f_i 表示点 i 变成 0 的最早时刻，这样就有初始 f_i=a_i，\forall (i,j)\in E,f_j\upd+f_i。

但是你注意到有的点会随着时间的流逝先 =0，又 >0，又 =0。

对于 DAG，源点到汇点的最长路 \le n，走过这条最长路之后，所有的点都一定被流动到了点权——换句话说，最多 n 个时间单位之后，这种情况不会再出现了。于是 n 次模拟后，我们就可以直接 dp 了。

时间复杂度 O(n^2)。

例 30-2. Luogu P8179. Tyres

有 n 种轮胎，需要用这些轮胎共跑 m 圈。对于第 i 种轮胎，它跑的第 j 圈（对每种轮胎单独计数）的代价为 a_i+b_i(j-1)^2，每相邻两圈使用了不同的轮胎，则需要增加 t 的代价。求最小代价。

当 t=0 时显然是可以用堆贪心的。

首先考虑朴素 dp。设 $f_{i,j}$ 表示前 $i$ 种轮胎，总共已经跑了 $j$ 圈的最小代价。 设 $w_i(x)=\sum\limits_{j=1}^x(a_i+b_i(j-1)^2)$，有转移方程 $f_{i,j}=\min\left\{f_{i-1,j},f_{i-1,0}+w_i(j),\min\limits_{k=1}^j\{f_{i-1,j-k}+w_i(k)+t\}\right\}$。把 $w_i(x)$ 拆开后可以 $O(nm^2)$ 转移。 考虑如何优化。利用 $\trick{30}$，尝试对于一种轮胎，寻找到一个 $k$ 满足第 $k$ 圈的代价不优于第 $1$ 圈的代价，即 $a_i+t\le a_i+b_i(k-1)^2$。这样对于 $\ge k$ 的圈是单调上升的，可以直接贪心。 注意到 $k=\lceil\sqrt t\rceil+1$ 一定满足上述不等式，故对于 $<k$ 的进行 dp，对 $\ge k$ 进行贪心，最后合并答案即可。 时间复杂度 $O(n^2t+m\log n)$。 --- ## 31. $(★★☆)$ 最值分治 > **对于序列内的一个数成为区间最值的极长区间，以该数为分界点，较短的那一段的长度和是 $\bm{O(n\log n)}$ 级别的。** ### 例 31-1. [CF1777F Comfortably Numb](https://codeforces.com/problemset/problem/1777/F) > 给定长度为 $n$ 的正整数序列 $a$，求 $\max\limits_{1\le l\le r\le n}\left\{\max\limits_{i=l}^r\{a_i\}\oplus\bigoplus\limits_{i=l}^ra_i\right\}$。 > $1\le n\le 2\times10^5,1\le a_i\le 10^9$。 考虑一个数 $a_i$ 成为区间最大数的极长区间 $[l_i,r_i]$，根据 $\trick{31}$，我们考虑枚举 $[l_i,i],[i,r_i]$ 中较短的一段，然后使用 01 Trie 处理即可。 下面来补充证明一下 $\trick{31}$ 的正确性。对于一个序列，我们全局最大值会贡献至多 $\dfrac n2$，对于被这个数划分成的两段，段内的最大值对应的极长区间显然不会跨越这个分界点，因此两侧的段最多贡献 $2\cdot\dfrac n4$。以此类推，就是 $\dfrac n2+2\cdot\dfrac n4+4\cdot\dfrac n8+\cdots=\dfrac n2\log n=O(n\log n)$。 时间复杂度 $O(n\log n\log a_i)$。 --- ## 32. $(★☆)$ 精度舍弃 > ***在某些情况下，计算时可以舍弃对最终答案没有较大影响的、精度较高的数。*** ### 例 32-1. [Luogu P11918. 考试 / Egzamin](https://www.luogu.com.cn/problem/P11918) > 一共 $n$ 道小题，第 $i$ 小题有 $p_i$ 的概率答对，$1-p_i$ 的概率答错。答对加一分，打错扣一分。每道题可以自由选择是否作答，最大化答对至少 $t$ 道题的概率。精度 $10^{-6}$。 > $1\le t\le n\le 5\times10^4,0\le p_i\le 1$，$p_i$ 的精度为 $10^{-9}$。 首先有一件显然的事情是我们降序 $p_i$ 后会选择一段前缀。 然后我们有一个朴素的 dp，$f_{i,j}$ 表示前 $i$ 个小题得 $j$ 分的概率。转移方程 $f_{i,j}=f_{i-1,j-1}\cdot p_i+f_{i-1,j+1} \cdot(1-p_i)$。 直接做是 $O(n^2)$ 的。那我们实际发现，由于一次选择是二项分布的，然后随着 $n$ 的增长，会呈现一个正态分布，那么区间两侧会有相当一部分概率很小的状态，那么由于这里对答案已经没有影响了，我们钦定一个 $\varepsilon$ 直接舍弃 $\le\varepsilon$ 的即可。然后状态数就够了。沉石鱼惊旋说状态数是在 $O(n\sqrt{\ln\varepsilon^{-1}})$ 级别的。 ### 例 32-2. [CF618G. Combining Slimes](https://codeforces.com/problemset/problem/618/G) > 给定一个长度为 $n$ 的网格。现在在网格上做操作。每次从右端向左压入一个数，有 $m$ 的概率为 $1$，$1-m$ 的概率为 $2$。当有两个相邻的 $x$ 时，会向左合并成一个 $x+1$。求直到无法操作时网格所有数之和的期望。精度需要 $10^{-4}$ 的相对误差。 > > $1\le n\le 10^9$，$10^{-9}\le m\le 1$。 首先根据期望的线性性，答案即为所有格子的期望之和。 设 $a_{i,j}$ 表示对于一个长度为 $i$ 的网格，其最左侧的数为 $j$ 的概率。那么转移需要前两个都出现 $j-1$，即有 $a_{i,j}=a_{i,j-1}\cdot a_{i-1,j-1}$。 设 $p_{i,j}$ 表示对于一个长度为 $i$ 的网格，其最左侧的数为 $j$，且 $j$ 不会被合并的概率。那么左侧第二个数必须不能是 $j$，所以有 $p_{i,j}=a_{i,j}\cdot(1-a_{i-1,j})$。 设 $f_{i,j}$ 表示最终的网格中**最右侧** $i$ 位中最左侧的数为 $j$ 时的期望和。考虑最终网格内数的情况。由于每次都会尽可能合并，因此对于相邻的两个数 $x,y$，一定满足 $x>y\lor x=1$。 于是当 $j\neq 1$ 时，可以直接枚举这 $i$ 位中左边第二个数 $k\ (k<j)$ 求期望，可以得到转移方程： $$ f_{i,j}=j+\dfrac{\sum\limits_{k=1}^{j-1}f_{i-1,k}\cdot p_{i-1,k}}{\sum\limits_{k=1}^{j-1}p_{i-1,k}} $$ 当 $j=1$ 时就可能有 $k>j$ 了。但这时 $j$ 之后第一个压入的数一定为 $2$。 于是再 dp。设 $b_{i,j}$ 表示对于一个长度为 $i$ 的网格，第一次压入的数为 $2$，且最左侧的数为 $j$ 的概率。由于我们只关心左侧第一个数，所以有 $b_{i,j}=b_{i,j-1}\cdot a_{i-1,j-1}$。 和上面同理，设 $q_{i,j}$ 表示对于一个长度为 $i$ 的网格，第一次压入的数为 $2$，且最左侧的数为 $j$，且它不会被合并的概率。同理有 $q_{i,j}=b_{i,j}\cdot(1-a_{i-1,j})$。 于是这时 $f_{i,j}$ 的转移也是同理的，即为： $$ f_{i,j}=j+\dfrac{\sum\limits_{k=2}^{m}f_{i-1,k}\cdot q_{i-1,k}}{\sum\limits_{k=2}^{m}q_{i-1,k}} $$ 于是最终的答案即为 $\sum\limits_{i=1}^np_{n,i}\cdot f_{n,i}$。 非常漂亮的 dp！可是时间复杂度全爆了！！！ 注意到题目要求的精度并不高，进一步发现： - 当 $j$ 足够大的时候，dp 值很小，可以忽略不计。 - 当 $i$ 足够大时，$p_{n,i}$ 几乎不变化。 于是考虑钦定一个阈值 $k=50$，对于所有 dp 的第二维，我们只计算到下标 $k$。而最终的答案计算，我们也只需要求出 $\sum\limits_{i=1}^np_{k,i}\cdot f_{n,i}$。 于是我们现在只需要处理出 $f_{n,[1,k]}$ 就好了。矩阵快速幂加速计算即可。 时间复杂度 $O(k^3\log n)$。 --- ## 33. $(★★★)$ 贡献和转积的一次项系数 > ***对于一些不好计算的贡献和，如果乘积是容易算的，可以考虑将原贡献 $\bm w$ 变为一次多项式 $\bm{wx+1}$，最后取一次项的系数即可。*** ### 例 33-1. [Luogu P6624. 作业题](https://www.luogu.com.cn/problem/P6624) > 给定 $n$ 点 $m$ 边的无向带权图，编号为 $i$ 的边的边权为 $w_i$，定义其生成树 $T=\{e_i\}$ 的价值 $f(T)=\left(\sum\limits_{i=1}^{n-1}w_{e_i}\right)\cdot\gcd\limits_{i=1}^{n-1}\{w_{e_i}\}$。求 $\sum f(T)$。 > $1\le n\le 30,1\le m\le\frac{n(n-1)}2,1\le w_i\le 152501$。 首先欧拉反演化简一下式子： $$ \begin{aligned} &\sum f(T)\\ =&\sum\limits_{T}\left(\sum\limits_{i=1}^{n-1}w_{e_i}\right)\cdot\gcd\limits_{i=1}^{n-1}\{w_{e_i}\}\\ =&\sum\limits_{T}\left(\sum\limits_{i=1}^{n-1}w_{e_i}\right)\cdot\sum_{d\mid w_{e_i}}\varphi(d)\\ =&\sum\limits_d\varphi(d)\sum\limits_{\substack{T\\d\mid w_{e_i}}}\sum\limits_{i=1}^{n-1}w_{e_i} \end{aligned} $$ 此时内部需要计算一个所有生成树边权和的和。 矩阵树定理可以处理边权积的和，如何转化？ 考虑 $\trick{33}$，将原来的边权 $w_i$ 变为一个关于 $x$ 的一次多项式 $w_ix+1$，这样的话我们求得的乘积是一个多项式，而一次项的系数恰好就是 $\sum w_i$！ 于是我们考虑计算在 $\bmod\ x^2$ 意义下的多项式即可。 这里补充一下一次多项式的四则运算： - $(ax+b)\pm(cx+d)\equiv(a\pm c)x+(b\pm d)\pmod{x^2}$。 - $(ax+b)(cx+d)\equiv(ad+bc)x+bd\pmod{x^2}$，这里二次项直接消掉了。 - 对于 $(ax+b)(cx+d)^{-1}$，设 $(cx+d)^{-1}=px+q$，则 $(cx+d)(px+q)\equiv(cq+dp)x+dq\equiv1\pmod{x^2}$，由于我们最后只剩下了常数项，所以一次项系数必然为 $0$，即 $cq+dp=0,dq=1$，这样就有 $q=\dfrac1d,p=-\dfrac c{d^2}$，即 $px+q=-\dfrac c{d^2}x+\dfrac 1d$，然后就可以做乘法了。 此外还有一个小优化是，我们对于一个枚举的 $d$，如果边数不足 $n-1$ 条，显然就不用管。 时间复杂度大约为 $O(n^2\sum d(w_i))$。 --- ## 34. $(★★★★)$ 数位 DP 优化贡献计算 > ***当个数和值域都很小，而答案可能很大时，可以考虑用数位 DP 处理答案的每一数位上的情况。*** ### 例 34-1. [CF1290F. Making Shapes](https://codeforces.com/problemset/problem/1290/F) > 给定 $n$ 个互不共线的向量 $(x_i,y_i)$，选用任意多个向量（每个向量均可重复使用），拼接形成一个多边形，要求： > > - 存在一个顶点和原点重合； > - 这是一个凸多边形； > - 多边形上的任意一个点的横纵坐标范围都在 $[0,m]$ 内。 > > 求有多少种本质不同的合法多边形，答案对 $998244353$ 取模。 > > $1\le n\le 5$，$1\le m\le 10^9$，$0\le |x_i|,|y_i|\le 4$，$(x_i,y_i)\neq(0,0)$。 首先，一种选择向量的方式和一种凸包是一一对应的。设向量 $(x_i,y_i)$ 选择了 $c_i$ 次，则答案等价于合法的序列 $c$ 数量，并有 $\sum\limits_{i=1}^nc_ix_i=\sum\limits_{i=1}^nc_iy_i=0$。 由于还有多边形坐标的限制，所以考虑拆开正负的贡献，也就是有 $0\le\sum\limits_{x_i>0}c_ix_i=\sum\limits_{x_i<0}-c_ix_i\le m\land 0\le\sum\limits_{y_i>0}c_iy_i=\sum\limits_{y_i<0}-c_iy_i\le m$。 接下来考虑如何计数。注意到 $n,a_i$ 都很小，利用 $\trick{34}$，一位一位考虑。 把 $c_i$ 拆成二进制位，则设 $f_{i,a,b,c,d,0/1,0/1}$ 表示当前状态下合法的序列 $c$ 数量，其中每一维分别表示： - 已经确定了最低的 $i$ 位； - 当前 $\sum\limits_{x_k>0}c_kx_k$ 贡献了 $a$ 的进位； - 当前 $\sum\limits_{x_k<0}-c_kx_k$ 贡献了 $b$ 的进位； - 当前 $\sum\limits_{y_k>0}c_ky_k$ 贡献了 $c$ 的进位； - 当前 $\sum\limits_{y_k<0}-c_ky_k$ 贡献了 $d$ 的进位； - 当前是否满足 $\left(\sum\limits_{x_k>0}c_kx_k\right)\bmod 2^i\le m\bmod 2^i$； - 当前是否满足 $\left(\sum\limits_{y_k>0}c_ky_k\right)\bmod 2^i\le m\bmod 2^i$。 然后枚举 $c$ 内每个数第 $i+1$ 位上的值即可。 设 $t$ 为进位数，则时间复杂度为 $O(t^42^n\log m)$，而 $t\le n\cdot |x_i|=20$。 ### 练习 34 - [HDU6953 Another thief in a Shop](https://acm.hdu.edu.cn/showproblem.php?pid=6953) --- ## 35. $(★★★)$ 抽屉原理转化 > ***当存在类似 $\bm{\le\dfrac 1k\times s}$ 之类约束的方案限制时，可以考虑转化为构造 $\bm{k}$ 种不受该约束的方案，其受约束的权值和恰好为 $\bm{s}$。*** ### 例 35-1. [CF2057G. Secret Message](https://codeforces.com/problemset/problem/2057/G) > 给定一个 $n\times m$ 的由 $\tt\#$ 和 $\tt .$ 构成的矩阵，设所有 $\tt\#$ 连通块的大小和为 $s$，周长和为 $p$。要求构造一种标记不超过 $\dfrac15(s+p)$ 个 $\tt\#$ 格的方案，满足对于所有 $\tt\#$ 格，其要么被标记，要么有一个与其有一条公共边的格子被标记。 > > $1\le n\times m\le 2\times10^6$。 这个题目限制给的 $\dfrac 15$ 很奇怪。 考虑 $\trick{35}$：如果我们不考虑这个限制的情况下构造出了 $5$ 种合法方案，并且这些方案的 $|S|$ 之和恰为 $s+p$，根据抽屉原理，其中必然存在至少一个方案满足 $|S|\le\dfrac15(s+p)$。 这也太牛了！那我们怎么找到这五个方案呢？ 考虑一种十字形的密铺： $$ \def\sq{\rule{10px}{10px}} \def\sq{\rule{10px}{10px}} \red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\\[-3px] \red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\\[-3px] \red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\\[-3px] \blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\\[-3px] \red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\\[-3px] \blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\\[-3px] \blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\red\sq\blue\sq\red\sq\\[-3px] \blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\blue\sq\red\sq\red\sq\\[-3px] \red\sq\red\sq\red\sq\blue\sq\red\sq\blue\sq\blue\sq\blue\sq\red\sq\\[-3px] $$ 发现，如果我们选择了所有十字形中心，那么剩余未被影响到的格子就会在边上，我们在另外选择这些点即可。 注意到这些十字形中心的坐标 $(i,j)$ 满足 $(i+2j)\bmod5$ 同余，所以我们按照这种方式五染色，就能得到 $5$ 种合法方案了！ 时间复杂度 $O(nm)$。 --- ## 36. $(★★)$ 前缀和或差分转化操作 > ***可以考虑用前缀和或差分转化看似无从下手的操作。*** ### 例 36-1. [AGC052 B. Tree Edges XOR](https://atcoder.jp/contests/agc052/tasks/agc052_b) > 给定一棵 $n$ 个节点的树，第 $i$ 条边的边权为 ${w_1}_i$。现可以任意次操作，每次可以选择一条边，将所有与其相邻的边异或上该边的权值。问是否可以将所有 ${w_1}_i$ 变为 ${w_2}_i$。 > > $1\le n\le 10^5,1\le w_{1_i},w_{2,i}\le2^{30}$，$n$ 为奇数。 模拟一下变换，发现前缀异或和是一个交换状物。 将节点 $x$ 的权值 $w'_i$ 设为根到 $x$ 的路径上的边权异或和。那么原来对一条边的操作，就等价于交换相邻节点的权值。于是我们直接比较 $\{w'_i\}$ 和 $\{{w_1}_i\}$ 是否相同即可。 注意由于根的问题，我们最后需要对所有节点异或上 $\left(\bigoplus{w_1}_i\right)\oplus\left(\bigoplus{w_2}_i\right)$（这也是为什么 $n$ 只能是奇数的原因）。 时间复杂度 $O(n)$。 ### 例 36-2. [Luogu P7962. 方差](https://www.luogu.com.cn/problem/P7962) > 给定一个长度为 $n$ 的单调不降的序列 $a$。任意次操作，每次可以选择一个 $i\in(1,n)$，执行 $a_i\gets a_{i-1}+a_{i+1}-a_i$。最小化 $a$ 的方差。输出最小值 $\times n^2$ 的结果。 > > $1\le n\le 10^4$，$1\le a_i\le 600$，$1\le n\times a_i\le 5\times10^5$。 考虑将 $a$ 序列差分，令 $d_i=a_{i+1}-a_i$。那么这个操作等价于交换了 $d_{i-1}$ 和 $d_i$。于是考虑 $a$ 的方差 $s^2$ 取到最小值时，$d$ 满足的性质。 事实上可以得到结论，$s^2\to\min$ 时，$d$ 会呈一个单谷的状态。证明推荐阅读 [这篇题解](https://www.luogu.com.cn/article/4csmcz4o)。然后可以进一步 dp。上述题解中也有说明。由于该题的后半部分不是我们要阐述的重点，故不多详细展开。 --- ## 37. $(★★★☆)$ 操作过程按位划分 > ***对于一些操作过程，可以考虑某一种操作对状态造成的影响，由此以某种特征状态对过程进行划分处理。*** ### 例 37-1. [AGC061E. Increment or XOR](https://atcoder.jp/contests/agc061/tasks/agc061_e) > 有一个非负整数变量 $x$，初值为给定的 $s$。另外有长度为 $n$ 的序列 $y$ 和 $c$。进行任意顺序、任意多次的以下操作之一： > > - $x\gets x+1$，花费代价为给定的常数 $a$。 > - $x\gets x\oplus y_i$，花费代价为 $c_i$。 > > 求 $x$ 从 $s$ 变为 $t$ 的最小代价，或报告无解。 > > $1\le n\le 8,0\le s,t,y_i<2^{40},0\le a\le 10^5,0\le c_i\le 10^{16}$。 考虑 $+1$ 操作带来的影响。 在二进制下，$+1$ 操作会使得末尾的一段极长的 $1$ 全部变成 $0$，并且更高一位变为 $1$。那么对于最低的若干位，它值的变化是 $s\to 0\to t$ 的。这样子的话我们只要考虑 $x$ 最低若干位初始是 $s$ 和 $0$ 的情况，而最终结果就是 $0$ 和 $t$。 于是可以设计状态 $f_{i,p,q,S}\ (p,q\in\{0,1\})$，表示对于最低的 $0\sim i-1$ 位，初值是 $s/0$，终值是 $t/0$，过程中所有实际异或的 $y_i$ 下标集合为 $S$ 的最小代价。 初值有 $f_{0,p,q,S}=\sum\limits_{i\in S}c_i+q\cdot a$。 考虑转移过程。首先最简单地，若对于第 $i$ 位，它是匹配的，则有 $f_{i+1,p,q,S}\gets f_{i,p,q,S}$。 接下来考虑产生新进位的情况。 我们首先从 $p$ 开始，做一次操作后，有第 $i$ 位为 $1$（更高的位不影响）；然后进行若干次进位操作，仍然保证第 $i$ 位为 $1$（更高的位不影响）；最后做一次操作，保证进到第 $i$ 位的时候满足了 $q$。 也就是有 $f_{i+1,p,q,\bigoplus\limits_{j=0}^kS_j}\upd{min}f_{i,p,1,S_0}+\left(\sum\limits_{j=1}^{k-1}f_{i,1,1,S_j}\right)+f_{i,1,q,S_k}$。可以类似 Dijkstra，每次取出未使用过的最小的 $f_{i,p,1,S}$ 转移即可。 最终答案就是 $\min\{f_{40,0,0,S}\}$。时间复杂度 $O(2^{2n}\log V)$。 ### 例 37-2. [UOJ 659. Picks loves segment tree IX](https://uoj.ac/problem/659) > 给定长度为 $n$ 的，对于非负整数变量 $v$ 的操作序列。其中有四种操作： > > - $\texttt{| }x$：$v\upd{or}x$。 > - $\texttt{\& }x$：$v\upd{and}x$。 > - $\texttt{∧ }x$：$v\upd{xor}x$。 > - $\texttt{+ }x$：$v\upd{+}x\pmod{2^{32}}$，此时保证 $x=1$。 > > $q$ 次询问，每次给出 $v,l,r,t$，求对 $v$ 依次进行下标为 $[l,r]$ 的操作后，二进制下从低到高第 $t+1$ 位的值。 > > **强制在线。** > > $1\le l\le r\le n\le 10^5,1\le q\le 6\times 10^5,0\le x,v<2^{32},0\le t<32$，$2\sec$。 同上一题一样，考虑 $+1$ 的影响后，我们可以对低位 $0$ 的个数划分状态。 记 $f_{k,i}$ 表示第 $i$ 次操作前最低的 $k+1$ 位都是 $0$，这些位同时第一次回到全 $0$ 的操作次数。这个有一个好处是，我们可以直接跳 $f_{k,i}$ 忽略掉 $+1$ 操作了。 那考虑如何计算最低 $k+1$ 位同时归零的时间。设 $g_{k,i}$ 表示一开始最低 $k+1$ 位呈现为 $100\cdots00$ 的形式，进行下标为 $[i,g_{k_i}-1]$ 操作后，最低 $k+1$ 位第一次全部同时变为 $0$，即呈现 $000\cdots00$ 的形式。 求 $f,g$ 都是容易的。 考虑答案求解。$g$ 是可以直接暴力跳的，而对于 $f$，我们建树后上树剖+二分即可。 时间复杂度 $O(n\log^2 V)$。 --- ## 38. $(★)$ Trie 交换子树 > ***可以通过 Trie 上交换子树来实现序列值域上的一些操作。*** ### 例 38-1. [AGC044C. Strange Dance](https://www.luogu.com.cn/problem/AT_agc044_c) > 编号为 $0\sim 3^n$ 的人围成一圈。现在有一个操作序列 $S$，有两种操作： > > - $S_i=\tt S$：表示对于第 $x$ 个人，他会走到第 $y$ 个位置，其中 $y$ 是 $x$ 三进制下每个数位 $\tt 12$ 翻转后得到的数。 > - $S_i=\tt R$：表示对于第 $x$ 个人，他会走到第 $(x+1)\mod 3^n$ 个位置。 > > 问最后每个人所在的位置。 > > $1\le n\le 12,1\le |S|\le 2\times 10^5$。 考虑把问题放到 trie 上处理，这里我们**从低到高**建树。 发现其实 $\tt S$ 对应着将每个节点的 $1,2$ 两个儿子交换，我们可以打懒标记处理。 而 $\tt R$ 操作，我们考虑从最低位向高位处理。发现对于同一个节点的三个儿子，我们容易想到轮换儿子，而变成 $0$ 的子树还需要处理进位，这一点我们递归下去即可。 时间复杂度 $O(3^n+n|S|)$。 ### 例 38-2. [CF1515H. Phoenix and Bits](https://codeforces.com/problemset/problem/1515/H) > 给定大小为 $n$ 的集合，$q$ 次操作或查询： > > - $\texttt{1}\ x\ y\ z$：将大小在 $[x,y]$ 的数按位与 $z$。 > - $\texttt{2}\ x\ y\ z$：将大小在 $[x,y]$ 的数按位或 $z$。 > - $\texttt{3}\ x\ y\ z$：将大小在 $[x,y]$ 的数按位异或 $z$。 > - $\texttt{4}\ x\ y$：查询 $[x,y]$ 内有多少个不同的数。 > > $1\le n\le 2\times10^5,1\le q\le 10^5$。 考虑使用动态开点权值线段树，但本质和 01 trie 类似。 对区间操作时，我们利用线段树分裂截出来这段，最后再合并回去。 xor 我们可以利用同上一个例题一样，直接交换左右子树即可。 对于 and，我们可以用 xor 和 or 代替。具体地，令 $S=2^{20}-1$，有 $x\text{\ and\ }y=((x\text{ xor }S)\text{ or }(y\text{ xor }S))\text{ xor }S$。 接下来只要考虑 or 即可。 我们相当于要对两个子树进行合并（只有一个子树是显然的），那么之间线段树合并即可。 时间复杂度 $O(n\log^2V)$，实际还有一点细节。 --- ## 39. $(★★)$ 弦交错判相交 > ***可以通过圆所截出的弦是否相交（即在圆上的端点是否交错），来判断圆内是否有直线相交。*** ### 例 39-1. [ABC263Ex. Intersection 2](https://atcoder.jp/contests/abc263/tasks/abc263_h) > 给定 $n$ 条互不平行或重合的直线 $a_ix+b_iy+c_i=0$，$n$ 条直线总共会有 $\dfrac{n(n-1)}2$ 个交点（包含在同一个位置的点，即相同位置算不同的点），求距离原点第 $k$ 近的交点的欧几里得距离。 > > $2\le n\le 5\times 10^4,1\le k\le \dfrac{n(n-1)}2,0\le|a_i|,|b_i|,|c_i|\le 10^3$。 考虑二分答案 $r$，此时问题就变成了圆 $x^2+y^2=r^2$ 内的交点数量。 运用 $\trick{39}$，就变成了圆内相交弦的对数。 将所有圆上的交点求出来后极角排序并离散化，按照更小的端点升序排序弦，做扫描线，用 BIT 维护区间内更大的端点的个数即为相交弦数量。 时间复杂度 $O(n\log n\log V)$。 ### 例 39-2. [CF607E. Cross Sum](https://codeforces.com/problemset/problem/607/E) > 给定 $n$ 条互不重合的直线 $y=\dfrac{k_i}{1000}x+\dfrac{b_i}{1000}$，两条不平行的直线之间会有一个交点（相同位置的交点多次计数），求距离点 $\left(\dfrac p{1000},\dfrac q{1000}\right)$ 前 $k$ 近的交点的欧几里得距离之和。 > > $2\le n\le 5\times 10^4 $，$1\le k\le\min\left\{3\times10^7,\dfrac{n(n-1)}{2}\right\}$，$0\le|k_i|,|b_i|,|p|,|q|\le10^6$。 同上一题类似，二分后转化成圆上端点的情况。 由于交点数只要到 $m$，可以使用线段树套 vector 维护。 时间复杂度 $O(n\log n\log V+m)$。 --- ## 40. $(★★)$ 钦定不操作元素 > ***对于序列内元素的操作，可以考虑钦定不操作的元素处理一些问题。*** ### 例 40-1. [ZR3287. 旋转排列问题](https://zhengruioi.com/problem/3287) > 给定一个 $1\sim n$ 的排列 $a$。每次操作可以选择一个 $x$，并将 $a_1$ 取出，插入到 $a_x$ 的后面一个。求有多少种长度为 $m$ 的操作序列 $x_1,x_2,\cdots,x_m$，使得最终的 $a$ 满足 $a_i=i$。答案对 $998244353$ 取模。 > > $2\le n,m\le 5000$。 考虑 dp。设 $f_{i,j}$ 表示操作了 $i$ 次，钦定了 $j$ 个元素此后不再操作，对应的合法操作序列个数。 发现我们可以钦定的这 $j$ 个元素可以形成 $a$ 的一个递增后缀，也就是我们把状态内的“钦定 $j$ 个元素”变成“钦定最后 $j$ 个元素”。 于是我们可以考虑第一个元素的情况进行转移。 - 如果钦定第一个元素做最后一次操作，那么可以转移 $f_{i+1,j+1}\upd+f_{i,j}$。 - 如果不是最后一次操作，那么只会插入到下标为 $1\sim n-j$ 的后面一个，也就是有转移 $f_{i+1,j}\upd+(n-j)f_{i,j}$。 时间复杂度 $O(n^2)$。 --- ## 41. $(★★★)$ 模糊答案考虑二进制位 > ***当要求输出答案只需要满足形如不超过两倍实际答案之类限制的时候，考虑将利用二的幂次缩小值域。*** ### 例 41-1. [ZR3254. 树上中位数](https://zhengruioi.com/problem/3254) > 给定一棵 $n$ 个节点的树，每个节点有点权 $a_i$，设点对 $(u,v)\ (u\le v)$ 的权值为其唯一简单路径上所有点权构成的可重集合 $S$ 中第 $\left\lceil\frac{|S|}2\right\rceil$ 小的数。求所有点对的权值和 $x_0$。你输出的答案 $x$ 只需要保证 $x_0\le x\le 2x_0$ 即可。 > > $1\le a_i\le n\le 5\times 10^5,2\sec,512\text{ MB}$。 将值在 $[2^{k-1},2^{k+1}-2]$ 内的数变为 $2^{k+1}-2$，发现此时的答案不超过原答案两倍。而且一件很好的事情是，点权只剩 $\log ⁡n$ 种了。 于是我们可以直接枚举中位数求解答案。使用长剖可以做到时间复杂度 $O(n\log ⁡n)$。 --- ## 42. $(★★★)$ 绝对众数与摩尔投票 > > *补充性质：* > > 1. *一个序列有且仅有一个绝对众数。* > > 2. *对于一个区间 $[l,r]$，在 $[l,\text{mid}]$ 和 $[\text{mid}+1,r]$ 中至少一个区间的绝对众数和 $[l,r]$ 相同。* > > 3. *一个序列的所有前缀共有 $\log$ 个本质不同的绝对众数。* > > 4. *一个序列的所有子段共有 $\log$ 个本质不同的绝对众数。* > > 5. *摩尔投票的信息是一个二元组，具有结合律。* > > > ***遇到绝对众数时，可以考虑其性质，或者维护摩尔投票信息。*** ### 例 42-1. [ARC159F. Good Division](https://atcoder.jp/contests/arc159/tasks/arc159_f) > 一个数列 $a$ 是好的，当且仅当可以若干次删除相邻两个值不同元素后，序列为空。 > 现给定一个长度为 $2n$ 的序列 $a$，将其划分为若干个非空子段，要求每一段都是好的。问这 $2^{2n-1}$ 种划分方法中有多少种是合法的。答案对 $998244353$ 取模。 > $1\le n\le 5\times 10^5$，$1\le a_i\le 2n$，$5\sec$。 显然一个好的序列当且仅当不存在绝对众数。 设 $\operatorname{abmode}(l,r)$ 表示 $a[l:r]$ 的绝对众数，若不存在，则 $\operatorname{abmode}(l,r)=0$。 那么就容易有暴力 dp。设 $f_i$ 表示前 $i$ 个数的答案，则 $f_i=\sum\limits_{j=1}^{i-1}[\operatorname{abmode}(2j+1,2i)=0]f_j$。对于一个区间 $[l,r]$，其所有子区间本质不同的绝对众数最多只有 $\log$ 种。考虑枚举绝对众数，则上式可以变为： $$ f_i=\sum\limits_{j=1}^{i-1}f_j-\sum\limits_k\sum\limits_{j=1}^{i-1}[\operatorname{abmode}(2j+1,2i)=k]f_j $$ 考虑分治。 在区间 $[l,r]$ 时，考虑计算 $f[l:\text{mid}]$ 对 $f[\text{mid}+1:r]$ 的贡献。假设枚举了绝对众数 $k$，那么可以将 $a_i=k$ 的位置变为 $1$，$a_i\neq k$ 的位置变为 $-1$，然后在这个区间内做一个前缀和，设为 $s_{k,i}$，那么对于 $i\in[\text{mid}+1,r]$，转移式子可以写作： $$ f_i\stackrel+\gets\sum\limits_{j=l}^{\text{mid}}f_j-\sum\limits_k\sum\limits_{j=l}^{\text{mid}}[s_{k,i}>s_{k,j}]f_j $$ 需要枚举的 $k$ 是可以直接预处理 $[l,\text{mid}]$ 的后缀和 $[\text{mid}+1,r]$ 的前缀。然后后面这个 $s_{k,i}>s_{k,j}$ 的限制可以 BIT 维护。这样子是 $T(n)=2T\left(\dfrac n2\right)+O(n\log^2n)$ 的，即 $O(n\log^3n)$。 然而注意到 $s_k$ 的值域范围很小，于是可以直接预处理一个 $g_k$ 出来： $$ g_{k,i}=\sum\limits_k\sum\limits_{j=l}^{\text{mid}}[s_{k,j}\le i]f_j $$ 于是时间复杂度变为 $T(n)=2T\left(\dfrac n2\right)+O(n\log n)$，即 $O(n\log^2n)$。 ### 例 42-2. [Luogu P8496. 众数](https://www.luogu.com.cn/problem/P8496) > 初始给定编号为 $1\sim n$ 的序列，分别给出初始有的 $l_i$ 个元素，序列可以为空。$q$ 次操作，维护这些序列： > > - $\texttt1\ x\ y$：在 $x$ 号序列末尾插入 $y$。 > - $\texttt2\ x$：删除 $x$ 号序列末尾的数字。 > - $\texttt3\ m\ x_1\ x_2\ \cdots\ x_m$：询问将 $x_1,x_2,\cdots,x_m$ 号序列拼接起来得到的序列的**绝对众数**，或报告不存在。 > - $\texttt4\ x_1\ x_2\ x_3$：新建一个编号为 $x_3$ 的序列，由 $x_1,x_2\ (x_1\neq x_2)$ 号序列的元素顺次拼接得到。 > > 保证操作合法，操作 4 的 $x_3$ 此前未使用，且此后序列 $x_1,x_2$ 不再使用。 > > $1\le n,q,\sum m,\sum l_i\le 5\times10^5$，$1\le x,y,x_i\le n+q$，$1\sec$，$1\text{ GB}$。 加入序列、删除序列、合并序列，显然可以对每个序列开一棵平衡树直接维护。 考虑询问。由于求的是绝对众数，可以维护摩尔投票的信息 $(\text{cur},\text{cnt})$，分别表示当前钦定的绝对众数，以及它还可以被抵消的次数。它有结合律，所以依旧可以放到平衡树上维护。查询时将每个序列的摩尔投票信息合并即可。 具体地，设两对信息为 $(x_0,y_0),(x_1,y_1)$，则定义他们的合并为： $$ (x_0,y_0)+(x_1,y_1)=\begin{cases} (x_0,y_0+y_1)&(x_0=x_1)\\ (0,0)&(y_0=y_1)\\ (x_0,y_0-y_1)&(y_0>y_1)\\ (x_1,y_1-y_0)&(y_0<y_1) \end{cases} $$ 最后需要检查是不是绝对众数，对每个序列开一个值域线段树来计数就可以了。合并序列的时候值域线段树也可以直接合并。 时间复杂度 $O((n+q)\log(n+q))$。 ### 练习 42 - [Luogu P11882. 彩虹糖 / Skittlez](https://www.luogu.com.cn/problem/P11882) --- ## 43. $(★★★☆)$ 延迟贡献 > ***如果可以将所有决策划分成「确定不再贡献的」和「可能再贡献的」两部分，dp 时可以考虑钦定一些位置，但此时不计算贡献，等到后续转移时再进行计算。*** ### 例 43-1. [Luogu P14364. 员工招聘](https://www.luogu.com.cn/problem/P14364) > 有 $n$ 个人，他们会按照一个排列 $p$ 在 $n$ 天内每天依次前往应聘。给定一个长度为 01 序列 $s$，若 $s_i=0$ 表示任意一人在第 $i$ 天应聘时都会失败；$s_i=1$ 表示任意一人在第 $i$ 天应聘时都会成功。 > > 同时有一个长度为 $n$ 的非负整数序列 $c$，若第 $i$ 个人暂未前往应聘，但此时已经有 $c_i$ 个人失败，则他会放弃，即他应聘那天自动视为失败。 > > 求所有能成功应聘至少 $m$ 人的排列方案数。对 $998244353$ 取模。 > > $1\le m\le n\le 500$，$s_i\in\{0,1\}$，$0\le c_i\le n$。 设前若干天已经有 $x$ 人失败，由于 $x$ 单调不降，因此当前 $c_i\le x$ 人是确定失败的，而 $c_i>x$ 的人不确定是否能够成功。 于是考虑 dp，设 $f_{i,j,k}$ 表示对于前 $i$ 天，当前有 $j$ 人失败，且当前有 $k$ 个位置的人 $c>j$，此时只考虑前 $i$ 天 $c\le j$ 的人的排列方案数。可以发现这 $k$ 个人暂时还没有造成贡献，需要后续转移的时候计算。 下面设 $\text{cnt}_i$ 表示 $c=i$ 的人数，$\text{sum}_i$ 表示 $c\le i$ 的人数。 讨论第 $i+1$ 天的人是成功还是失败： - $s_{i+1}=0$，此时必然失败。 讨论第 $i+1$ 天的人 $p_{i+1}$ 对应的 $c_{p_{i+1}}$ 和 $j+1$ 的大小。**然后这时，将 $\boldsymbol{k}$ 个人中满足 $\boldsymbol{c=j+1}$ 的算入贡献**。枚举这 $k$ 个人中有 $x\ (x\in[0,k])$ 个满足 $c=j+1$。 - $c_{p_{i+1}}>j+1$，这时对于前 $i+1$ 个人，有 $k-x+1$ 个满足 $c>j+1$（因为需要加上当前这个人）。转移时需要乘上从 $k$ 个已钦定位置中选择 $x$ 个位置，以及从 $\text{cnt}_{j+1}$ 个人中选择 $x$ 个人任意排列的组合数，即： $$ f_{i+1,j+1,k-x+1}\upd+ f_{i,j,k}\cdot\binom kx\cdot\binom{\text{cnt}_{j+1}}x\cdot x! $$ - $c_{p_{i+1}}\le j+1$，这时对于前 $i+1$ 个人，有 $k-x$ 个满足 $c>j+1$。转移除了要乘以上一种情况的系数外，还需要乘一个第 $i+1$ 天可能的人，即满足 $c\le j+1$ 且前面没出现过的人总数。有转移： $$ f_{i+1,j+1,k-x}\upd+ f_{i,j,k}\cdot\binom kx\cdot\binom{\text{cnt}_{j+1}}x\cdot x!\cdot(\text{sum}_{j+1}-i+k-x) $$ - $s_{i+1}=1$，此时有可能成功。于是对 $c_{p_{i+1}}$ 和 $j$ 进行讨论。 - $c_{p_{i+1}}>j$，这时必然成功，$j$ 不变，直接转移： $$ f_{i+1,j,k+1}\upd+ f_{i,j,k} $$ - $c_{p_{i+1}}\le j$，这时直接放弃，$j$ 变为 $j+1$。和 $s_{i+1}=0\land c_{p_{i+1}}\le j+1$ 的情况类似，除了乘上排列组合数的系数外，还需要乘上满足 $c\le j$ 且前面没出现过的人的总数。有： $$ f_{i+1,j+1,k-x}\upd+ f_{i,j,k}\cdot\binom kx\cdot\binom{\text{cnt}_{j+1}}x\cdot x!\cdot(\text{sum}_j-i+k) $$ 于是答案即为 $\sum\limits_{i=0}^{n-m}f_{n,i,n-\text{sum}_i}\cdot(n-\text{sum}_i)!$，即还剩下没算贡献的再任意排列一下。 由于一定有 $x\le\text{cnt}_{j+1}$，所以均摊下来的时间复杂度为 $O(n^3)$。 --- ## 44. $(★★☆)$ 可行决策转排列决策 > ***如果初始状态下的某些决策，在后续状态下因为其他决策影响，导致该决策不合法或没有影响，可以考虑事先钦定所有决策的顺序，然后依次执行当前仍旧合法的决策。*** ### 例 44-1. [ARC114E. Paper Cutting 2](https://atcoder.jp/contests/arc114/tasks/arc114_e) > 给定一张 $h\times w$ 的网格，有且仅有 $(x_0,y_0)$ 和 $(x_1,y_1)$ 两个格子被涂黑。设当前的剩余网格大小为 $p\times q$，则每次可以从 $p-1$ 条横线和 $q-1$ 条竖线中，等概率随机选出一条线，并沿其将网格切开，并保留两个黑格子都在的那张网格上，否则操作结束。求期望可以进行的操作次数，对 $998244353$ 取模。 > > $1\le h,w\le 10^5$，$1\le x_0,x_1\le h$，$1\le y_0,y_1\le w$。 这个纸张缩小的限制很烦，因为我们有的初始能做的决策到后面不合法了。考虑运用 $\trick{44}$，将操作转化为：初始横纵一共 $h+w-2$ 条直线，随机一个长度为 $h+w-2$ 的排列，然后依次切当前可以切的直线，不合法的操作忽略。 根据期望的线性性，期望操作次数等于每条线被切割的概率之和。 然后对于极小的可切出的矩形，其四侧的直线，由于整体上互不影响，于是可以分开考虑。对于一条直线，如果它排在另外 $k$ 条之后切，就会产生 $\dfrac 1{k+1}$ 的贡献。于是四侧分别枚举并求和即可。时间复杂度 $O(h+w)$。 ### 例 44-2. [ARC165E. Random Isolation](https://atcoder.jp/contests/arc165/tasks/arc165_e) > 给定一棵 $n$ 个点的无根树。每次操作，将所有大小 $\ge k$ 的连通块中分别等概率随机删去一个点，直到不存在这样的连通块为止。求期望操作次数，对 $998244353$ 取模。 > > $1\le k<n\le 100$。 由于多次操作一个点是没有意义的，而且操作需要的约束和上一题类似。于是我们可以将操作过程同样地刻画：生成一个排列出来，然后按照排列依次看这个点，如果所在连通块大小 $>k$ 就删，否则不管。那么原问题的答案，就是这个排列上被操作的点的个数的期望。 考虑一个以 $x$ 为根的连通块，大小为 $i$，如果说这样一个连通块会产生，那么和该块相邻的 $j$ 个点都需要在 $x$ 之前删掉。这 $i+j$ 个点以外的点都没有影响。那么对于这些点，总共有 $(i+j)!$ 种排列，而 $j$ 个点先删的有 $i!j!$ 种，故概率为 $\dfrac{i!j!}{(i+j)!}=\dfrac1{\binom{i+j}{j}}$。 于是考虑 dp，设 $f_{u,i,j}$ 表示以 $u$ 为根的连通块大小为 $i$，与之相邻的有 $j$ 个点的连通块数。这里为了方便操作，$j$ 是不考虑 $u$ 的父亲的，于是可以树上背包转移。设 $u$ 的儿子为 $v$，对应枚举的大小和相邻点数为 $x,y$，则有： $$ f_{u,i+x,j+y}\overset+{\gets}f_{u,i,j}\cdot f_{v,x,y} $$ 初值 $f_{u,1,0}=1$。由于 $u$ 不选任何儿子也是会有相邻点的，于是还有 $f_{v,0,1}=1$。 最终计算的答案，就是将所有的连通块产生的贡献加起来，即： $$ \sum\limits_{i=1}^n\sum\limits_{x=k+1}^{\text{sz}_i}\sum\limits_{y=0}^{\text{sz}_i-x}\dfrac{f_{i,x,y}}{\binom{x+y+[i\neq1]}{y+[i\neq 1]}} $$ 里面有个 $[i\neq 1]$ 是在特判前面没考虑的父亲。 时间复杂度 $O(n^2k^2)$。