题目随记
https://47.94.97.204/contest/1694/problem/4
题目中直接给出了 $\frac a2$ 时间复杂度 $\log V$ 的提示太明显了，直接上套路即可。
https://www.luogu.com.cn/problem/P8036
由于 $[a, b]$ 一定有界，所以二分的条件应当是在 $[a, b]$ 之间，而不是单纯的大于小于。
https://www.luogu.com.cn/problem/CF1290F
数位 DP 可以对不止一个数 DP，可以使用状压的方式对多个数进行 DP。
没有做出来的究极无敌逆天简单题
CF1841C Ranom Numbers
https://www.luogu.com.cn/problem/CF1841C
本题关键：发现性质优化暴力。
最近增量题做的比较多，看到这个题马上就去考虑增量，然后一直讨论没有讨论出来。
实际上有用的字符就只有开头和结尾的，把他们找出来之后暴力跑就行了。
好题
P11256 [GDKOI2023 普及组] 置换
https://www.luogu.com.cn/problem/P11256
鲜花：谁家 PJ 组考这么困难的题。
有一个听说很典的结论，但是我不知道：
-
对于原图上长为 $m$ 的置换环，操作 $k$ 次之后，对应 $\gcd(k, m)$ 个长度为 $\frac{m}{\gcd(k, m)}$ 的环。
-
证明：操作相当于把每个点从往 $k$ 个点后连边，连出来的环数就是产生环的数量。
显然，一个大环分裂出的小环大小一定相同，故我们只需要对相同长度小环考虑即可。考虑 DP，定义 $F(i, j)$ 代表长度为 $i$ 的环已经选了 $j$ 个的方案数，转移考虑枚举 $x$，代表 $Y$ 中 $x$ 个长度为 $i$ 的置换环构成了 $X$ 中的大置换环。为了避免算重，我们钦定第 $j$ 个置换环是一定要选的，当然 $x$ 需要满足 $\gcd(i\times x, k) = x$。对于每个小环有 $i$ 种排列方式，小环之间有 $x!$ 种排列方式，那么贡献为 $i \times x!$，由于二者都是环，所以需要除以 $i\times x$ 最终的转移方程为：
$$F(i, j) = \sum_{x \le j, \gcd(\times x, k) = x} F(i, j – x) \times \binom{j – 1}{x – 1} \times \frac{i^x \times x!}{i\times x}$$
乘上 $\binom {j – 1}{x – 1}$ 是因为我们钦定了第 $j$ 个置换环一定要选，而剩下的 $x – 1$ 个置换环需要从 $j – 1$ 个置换环当中选择。最终的答案为 $\prod_{i = 1}^n F(i, cnt(i))$，其中 $cnt(i)$ 代表 $Y$ 中长度为 $i$ 的置换环个数。
124oj3074 瞬(teleport)
http://124.221.194.184/contest/136/problem/3074
考虑定义 $F(x, p, k)$ 代表当前在节点 $x$，放置的分身在 $p$，还有 $k$ 个分生可以用的最小距离。
有一个结论，若 $k > \log_2 n$ 的答案都是一样的，可以通过重链剖分证明。
CF982F The Meeting Place Cannot Be Changed
https://www.luogu.com.cn/problem/CF982F
trick: 对于环求交问题，可以先找到一个主环，然后对于环上的每一个节点找到不经过环上的边能够走到最远的节点，将这个两个节点之间的点标记为不合法，只需要遍历每个节点一次。
由于某人会任意选择起点然后走无穷多步，说明图上的每一个节点都能够走到一个环上，要求必经之路相当于就是求这个有向图所有环的交。
求有关于环的问题，第一时间可能会想到 DFS 生成树，但有向图的 DFS 生成树并没有什么很好的性质，我们不得不抛弃这一想法。
有一步非常套路的想法是现在图上随便找一个环（题目保证一定有环），接着进行某些处理得到答案，笔者正是卡在了这一步。思考如何找到交是非常不容易的，正难则反，考虑能否找到不是交的边。
对于主环上每一个节点，我们可以找到其不经过环上的边能够走到的最远的节点，然后将这两个节点之间的节点标记为不合法，正确性是显然的，直接暴力做的时间复杂度是 $O(n ^2)$。实际上每个节点第一次被访问到才是有意义的。如果一个节点第二次被访问，那么第二次访问到达的最远的节点一定是第一次访问到达的，所以我们证明了一个节点至多只会被访问一次。
但请读者认真思考一下便会发现上述证明其实是有误的，因为对于两个不同的节点 $A$ 和 $B$ 他们对 “远” 的定义不同，对于一个在 $A$ 和 $B$ 之间的节点 $C$，在 $A$ 作为起点时 $dis(A, C)$ 是要小于 $dis(B, C)$ 的，但在第一次访问的时候 $C$ 并不是访问到最远的节点，如下图所示：
为了解决这个问题，我们不妨钦定原图一定有交，若原图一定有交那么上述策略可以得证，如果最终找到的交删去之后依然有环存在，则说明问题无解，需要在结尾加一个 check。
B. 2025–[炼石计划–NOIP模拟二十二]–T2–原神
https://mna.wang/contest/1809/problem/2
显然有暴力，对于每一个 $x$，求解以下式子：
$$ \sum_{i = 0}^{n} \binom{x – 1}{x – 1 – i}\binom{m – i}{n – i} \times a_i $$
其中 $a_i$ 为 search 函数返回位置为 $i$ 时，check() 被调用的次数。这样的暴力似乎是没有办法做的，考试的时候也卡在了这一步。
对于计数题，有两种方法处理这种不是很能直接化简的问题：
- 拆贡献
- 换做法。
先不考虑换做法，考虑拆贡献。对于一般组合数的题目，贡献不是很好拆的，但这个题的特殊之处在于有许多 $a_i$ 都是一样的。对于所有相同的 $a_i$ 无论 $x$ 落在相同 $a_i$ 中的任何位置，$a_i$ 造成的贡献是唯一的，不妨考虑若 $x$ 落在相同区间中的方案数是多少。直接做很难考虑 $x$ 超过了区间右端点的情况，为了解决这个问题，我们可以将 $a$ 数组差分，则钦定贡献在左端点处计算往后所有的贡献即可，只有 $\log n$ 种不同的取值。运用了计数问题如果算重，钦定转移的思想。
$$ \sum_{i = 0}^{n} \Delta a_i \sum_{j = 1}^{x} \binom{j- 1}{i – 1}\binom{m – j}{n – j} $$
$x$ 每增加一，式子只会增加一项，暴力维护即可。
[ABC232G] Modulo Shortest Path
https://www.luogu.com.cn/problem/AT_abc232_g
一个使用了最短路的思想但是并没有使用任何最短路的数据结构题解。
考虑 Dijkstra 暴力跑这个问题是怎么实现的，djk 每次会选择一个离起点集最近的点然后将其加入点集，由于题目中图是完全图，图中每个点都有可能是离起点最近的点，这启示我们用数据结构寻找全局最小值然后将其加入点集。
考虑具体怎么做，首先如果一个节点已经被加入点集，那么他的权值应当为 $\infty$，这一点是毋庸置疑的。
接着我们考虑从每一个节点出发，能够对未加入点集中的点造成什么样的影响。设当前加入点集的节点为 $u$，当前节点最短路为 $f(u)$，分两种情况讨论，若 $b_v + a_u < m$，则 $f(v) \gets \min(f(v), f(u) + a_u + b_v)$，否则 $f(v) \gets \min(f(v), f(u) + a_u + b_v – m)$，我们是可以提前将每个节点通过 $b$ 从小到大排序，这样每次操作我们可以二分出第一个 $a_u + b_v \ge m$ 的位置 $pos$，用 $f(u) + a_u – m$ 对 $[pos, n]$ 取最小值，由于前者一定比后者优，用 $f(u) + a_u$ 对全局取最小值。
现在我们已经可以使用线段树解决这个问题了，对于每个区间，分别记录最小值、最小值位置、最小的 $b$ 值，最小 $b$ 所在位置，即可维护这个问题。
由于笔者想题的时候 nt 了，所以求的是 $n \to 1$ 的最短路，核心和上述思路一样。
【PNR #7】排列计数
https://pjudge.ac/contest/1811/problem/21858
https://qoj.ac/contest/1644/problem/8351
弱化版问题：https://vjudge.net/problem/CSES-1075#author=GPT_zh
由于我们没有办法确定哪些数是被填过的，所以传统的定义 $F(i, j)$，前 $i$ 个数，最后一个是 $j$ 的 DP 是不可行的。
DP 需要做的是状态的转移，自然我们需要检查一个状态是否合法，如果一个状态合法，那么形如 $|a_i – a_{i + 1}| = k$ 的元素对是不存在的，不妨直接设为状态；但是只是这样依然无法转移。不妨先考虑弱化版问题，帮助我们理解。
先考虑弱化版问题：给定 $n$，你要求出有多少个长度为 $n$ 的排列满足相邻两项的差不为 $1$，定义 $F(i, j)$ 代表前 $i$ 个数字，有多少个不合法的相邻的对，但这样很显然是不完善的，因为有可能 $i – 1$ 和 $i – 2$ 是靠在一起的，此时插入 $i$ 会和 $i – 1$ 形成一个新的不合法对。为了规避这种特殊情况，考虑再记一维 $0/1$ 代表是否存在 $i$ 和 $i – 1$ 靠在一起的对。
定义 $F(i, j, 0/1)$ 前 $i$ 个数字有 $j$ 和不合法的对，$i – 1$ 和 $i$ 是否在一起。
对于需要满足特定条件的排列问题，可以考虑记录不合法的数量当作状态。
[ABC134F] Permutation Oddness
https://www.luogu.com.cn/problem/AT_abc134_f
看见绝对值相关题目，考虑拆贡献，对于一个数字 $p_i$ 他的贡献可能是 $+p_i$ 也可能是 $-p_i$，这启示我们从前往后依次决定每个数字和哪一个配对，考虑 DP 定义 $f(i, j, k)$ 为前 $i$ 个数，已经匹配了 $j$ 个数，怪异度为 $k$，转移需要分 $4$ 中情况讨论，自己和自己配对，二者与前面配对，二者与后面配对，一个与前面，一个与后面配对。
124oj3038 tamaya
http://124.221.194.184/contest/135/problem/3038
如果时间戳靠后的操作对时间戳靠前的操作有覆盖作用，可以考虑倒序操作。
对于每个询问 $L$，$R$，$x$ 初始时令 $[l, r] = [x, x]$，从 $R$ 到 $L$ 枚举每个区间，如果枚举到的区间与 $[l, r]$ 有交，则取并，枚举完成后查询 $[l, r]$ 中的最大值即可，时间复杂度 $O(nq \log n)$。
考虑优化这一过程，可以预处理出在 $i$ 之前第一个包含 $i$ 的区间，然后倍增，但这样也需要处理每一个询问在 $R$ 之前第一个包含 $x$ 的区间，时间复杂度 $O(q \log n)$。
P8163 [JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)
https://www.luogu.com.cn/problem/P8163
这个题如果同时思考 $A_j < B_j$ 和 $A_j > B_j$ 脑子是会爆炸的，对于这种有操作会莫名其妙夹在在一起的题，应当考虑化简问题，只考虑其中一种做法，并尝试推广到全局。也就是非常有启发性的子任务 $5$。
尝试只考虑 $A_j < B_j$ 的问题该如何处理，我们可以使用 multiset 维护出对于每个点，其只乘坐一次列车能够到达最远的点是哪一个 $ri_i$；那么对于每一次询问，初始时 $[l, r] = [s, s]$，做一次列车相当都对 $r$ 执行如下操作：$r \gets \max_{i\in[l, r]} ri_i$，需要用到 ST 表，如果暴力更新 $r$ 那么复杂度是 $O(qn\log n)$，考虑优化，有一个很显然的想法是使用倍增 $ri(i, j)$ 代表点 $j$ 走了 $2^i$ 步最远能够到达的右端点，按照平时 $ri(i, j) = ri(i-1,ri(i-1,j))$ 转移是不行的，因为 $[j, ri(i – 1, j)]$ 中所有的值都可能影响 $ri(i, j)$ 的取值，所以需要用到 ST 表进行区间查询最大值时间复杂度 $O(n \log^2 n) – O(n \log n)$。
回到原问题，本质上我们是要依次扩展区间 $[l, r]$，对于 $A_j >B_j$ 的情况和刚才的区别在于倍增中区间查询的左端点不是不变的了，令 $le(i, j)$ 代表点 $j$，最少转 $2^j$ 次车能够到达的最远左端点，转移时查询的区间变为 $[le(i – 1, j), ri(i – 1, j)]$，本质上还是对于一个区间进行倍增转移，与子任务 $5$ 的做法没有本质区别。
P9527 [JOISC2022] 洒水器
https://www.luogu.com.cn/problem/P9527
注意到 $D \le 40$ 有一个很显然的思路，对于每一次修改操作，暴力向上跳 $k$ 级祖先，然后利用类似于中途相遇的思想去统计问题，定义 $f(u, d)$ 为离节点 $u$ 距离 $= d$ 的操作乘积。但是这样子会算重，在计数问题中算重有三种解决方法：
- 换做法，考虑暴力维护 $g(u, d, v)$ 为 $f(u, d)$ 抛去子树 $v$ 的答案，时间复杂度是 $O(qd^2)$ 无法通过，我就卡在了这一步。
- 容斥，这道题的答案不满足可减性（模数不是质数）。
- 钦定在某一个位置计算贡献（往往是端点）。
第三点是最容易忽视的一点，其实这个问题在做区间计数问题出现的次数比较多，在这类问题中，往往会钦定区间在右端点的位置进行转移，这便是第三点的体现。
回到这个问题，对于两个点 $u$ 和 $v$，他们会在 $lca(u, v)$ 处开始重复计算贡献，这是端点之一。令这一次操作的距离为 $d$，$a$ 是 $u$ 的若干级祖先。当 $dis(a, u) + dis(a, v) = d – 1$ 或 $dis(a, u) + dis(a, v) = d$ 时是另一个端点。显然选取前者对我们没有任何好处，考虑选择后者。
现在的问题便可以做了，每次修改操作，在对应的节点上记录一下对应的 $d – 1 – dis(a, u)$，这样对于每个 $dis(a, v)$ 快速查就可以了。
P6345 [CCO2017] 接雨滴
https://www.luogu.com.cn/problem/P6345
考虑拆贡献，考虑一个位置的贡献是什么，令 $pre_i$ 为前 $i$ 个数字中，大于 $a_i$ 且最大的数；令 $suf_i$ 为 $i \sim n$ 中大于 $a_i$ 且最大的数，如果不存在这样的数则值为 $0$，那么 $f(b) = \sum min(suf_i, pre_i) – b_i$。
此时便可以考虑区间 DP 还要配上可行性背包，$f_{i, l, r, k}$ 代表考虑了前 $i$ 大的数，已经被填过的区间为 $[l, r]$，值 $k$ 能否被构成，时间复杂度 $O(\frac{n^4v}w)$，显然记录具体是哪一个区间是非常 trivial 的，我们没有必要这样，卡在了这里不知道干嘛了。
枚举区间很显然是不能够给我们带来任何好处的，考虑 $f_{i, j, k}$，前 $i$ 大的数，已经填了长度为 $j$ 的区间，$k$ 能否被构成，转移是非常普通的，时间复杂度为 $O(\frac{n^4v}w)$。转移是从 $f_{i – 1, j – d, k – d \times a_i}$ 转移到 $f_{i, j, k}$。但这里还能够将每次枚举的转移常数转化为完全背包问题，也就是我们每次会枚举的 $d$，实际上可以看成由 $f_{i – 1, j – 1, k – a_i}$ 转移到 $f_{i, j, k}$，的完全背包，省略了枚举 $d$，时间复杂度为 $O(\frac{n^3 v}w)$。
当然对于每一个相同的 $a_i$ 只需要转移一次，时间复杂度可以做到 $O(\frac{n^2v^2}w)$，都需要用到 bitset 优化。
P6345 [CCO2017] 接雨滴
https://www.luogu.com.cn/problem/P6345
考虑拆贡献，考虑一个位置的贡献是什么，令 $pre_i$ 为前 $i$ 个数字中，大于 $a_i$ 且最大的数；令 $suf_i$ 为 $i \sim n$ 中大于 $a_i$ 且最大的数，如果不存在这样的数则值为 $0$，那么 $f(b) = \sum min(suf_i, pre_i) – b_i$。
此时便可以考虑区间 DP 还要配上可行性背包，$f_{i, l, r, k}$ 代表考虑了前 $i$ 大的数，已经被填过的区间为 $[l, r]$，值 $k$ 能否被构成，时间复杂度 $O(\frac{n^4v}w)$，显然记录具体是哪一个区间是非常 trivial 的，我们没有必要这样，卡在了这里不知道干嘛了。
枚举区间很显然是不能够给我们带来任何好处的，考虑 $f_{i, j, k}$，前 $i$ 大的数，已经填了长度为 $j$ 的区间，$k$ 能否被构成，转移是非常普通的，时间复杂度为 $O(\frac{n^4v}w)$。转移是从 $f_{i – 1, j – d, k – d \times a_i}$ 转移到 $f_{i, j, k}$。但这里还能够将每次枚举的转移常数转化为完全背包问题，也就是我们每次会枚举的 $d$，实际上可以看成由 $f_{i – 1, j – 1, k – a_i}$ 转移到 $f_{i, j, k}$，的完全背包，省略了枚举 $d$，时间复杂度为 $O(\frac{n^3 v}w)$。
当然对于每一个相同的 $a_i$ 只需要转移一次，时间复杂度可以做到 $O(\frac{n^2v^2}w)$，都需要用到 bitset 优化。
CF1845E Boxes and Balls
https://www.luogu.com.cn/problem/CF1845E
首先如果移动 $k$ 次能够达成某种状态，那么 $k + 2$ 次也可以。
对于这种给定若干操作计数问题可以讨论最终状态的合法性。
用 $a$ 描述状态，$a_1 < a_2 < \cdots < a_{|a|}$ 描了所有有球的位置，令 $a$ 表示初始状态，$b$ 描述结束状态，则有 $|a| = |b|$
考虑 $a$ 变为 $b$ 的最小操作步数，则 $f(b) = \sum |a_i – b_i|$，如果有解则必然满足 $2 \mid k – f(b)$。
定义 $f_{i, j, k}$ 代表前 $i$ 个位置有 $j$ 个 $1$ 且 $f(b) = k$ 时的方案数是多少，可以从 $f_{i, j, k}$ 转移到 $f_{i + 1, j + 1, k + |i + 1 -b_{j}|}$。
直接做是 $O(n^3)$ 的，但是我最开始自己做的时候以为这样的状态会漏掉东西，主要是没有考虑到 $f(b)$ 的值其实能够帮助我们确定 $b$，再加之并没有想到操作次数最小这个东西。
每次都枚举一堆 $j$ 是没有意义的，如果想把 $x$ 个 $1$ 从 $i$ 挪到 $i + 1$，至少需要 $x^2$ 步，所以只需要枚举 $\sqrt k$ 这个两级就行。有人认为这种问题是关于不降序列对应位置距离之和，有经典套路：在每个间隔处统计答案。也可以说是每个间隔的花费。
124oj3303 小 T 与灵石（stone）
http://124.221.194.184/contest/135/problem/3033
此题关键在于：将询问的无效信息删去，只保留必要信息。
虽然询问给定了大小为 $k$ 的点集，实际上很多的点都是无用的，只需要考虑相聚最远的两个点，也就是这个点集的“直径”。
设直径的两个端点为 $x$ 和 $y$，设 $x$ 的深度大于 $y$，直径中点为 $m$，则 $m$ 把树分成了两个部分，其一为 $m$ 的子树内，子树内的点到 $x$ 的距离就是答案，反之亦然。子树内和子树外在 $dfn$ 上一定是一段区间，因为在计算 $dis$ 的时候会有 LCA 的影响非常麻烦，考虑点分治配上优先队列，维护这一过程。
其实没有必要，对于一个直径，$max(dis(u, x), dis(u, v)) = \frac {len}2 + dis(u, m)$，可以用经典的的树形 DP 解决问题。
CF1661F Teleporters
https://www.luogu.com.cn/problem/CF1661F
这个问题关键在于：从答案的增量考虑问题。
结论1： 一定是在相邻的两个传送机平均分配新的传送机。
社 $f(x)$ 代表相邻的两个传送机中插入 $x$ 个新的传送机的价值，$g(x) = f(x) – f(x + 1)$，人话 $g(x)$ 是 $f(x)$ 的增量，可以证明 $g(x)$ 是单调递增的。
我们可以用一个优先队列记录每个相邻的传送机带来的贡献，配合上二分，但这样做时间复杂度是有问题的。
考虑我们用优先队列解决问题的本质，他一定会先选择减量大的相邻的传送机，且选过的 $g(x)$ 一定不小于没有选定的 $g(x)$，满足单调性，这启示我们二分减量。
对于每一个相邻的传送机，我们都可以二分出 $g(x)$，这便完成了 check，本题完结。
时间复杂度 $O(n \log^2 n)$。
P3589 [POI2015] KUR
https://www.luogu.com.cn/problem/P3589
此题关键之处在于：将出现次数转化为可能出现的位置数量，剩下的内容比较套路。
不妨从特殊情况开始思考。
若 $m = 1$ 时，答案是显然的；若 $m = 2$，我们可以将满足 $s_i = t_1$ 的位置标记出来，接着再从标记过的位置中重新标记找到 $s_{i + 1} = t_2$，最终标记的数量便是我们需要的答案。对于 $m$ 更大的情况，依然可以这样处理。
现在问题转化为：给定若干个区间，求这些区间的交。由于 $n$ 是 $10^9$ 级别的，所以需要用离散化和差分，实际上这样子实现起来比较复杂，可以转而维护不合法区间的并。
现在的问题是如何求出这些区间。
设 $t$ 在 $s$ 中匹配的位置为 $i$，有 $t_{x + 1} = s_{i + x}$，下标从 $0$ 开始。
- 当 $t_{x + 1} = 0$ 时，有 $0 \le (ai + ax + b) \bmod n < p$，化简可得 $-ax-b\leq ai <p-ax-b$。
- 否则，有 $p \le (ai + ax + b) \bmod n < n$，化简可得 $p – ax – b \le ai < n – ax – b$。
由于是在模 $n$ 意义下，可能会出现类似 $p – ax – b > n – ax – b$ 的情况，此时 $ai$ 的取值范围为 $[p – ax – b, n – 1] + [0, n – ax – b)$，对于$t_{x + 1} = 0$ 同理。
蠢蠢的笔者看了别的题解自己推式子的时候把 $a$ 除了过去，然后发现以 $i$ 为下标的序列构成的区间根本不是连续的！思考了半天，其实不除过去就行了，因为当 $\gcd(a, n) = 1$ 时，$ai \bmod n$ 与 $i \in[0, n – 1]$ 的取值一一对应，故我们只需要统计有多少个 $ai$ 满足条件即可。
当然如果你这样统计完之后你会发现你算出来的结果比标准答案要大，这是由于我们把 $[n – m + 1, n – 1]$ 这一坨合法的答案统计进去了，减掉即可。
困难题
124oj3075 LJJ的生日礼物（gift）
http://124.221.194.184/contest/136/problem/3075
https://www.cnblogs.com/dysyn1314/p/14301993.html
代办
https://www.luogu.com.cn/problem/P8569
https://www.luogu.com.cn/problem/P11256