肝完了/ll。
在 U 群看到了 sys 的博客，感觉很有道理，以后还是不要给自己设限，多做做难题。
P8338 [AHOI2022] 排列
Analysis
好困难。
设 \(P\) 所有置换环大小为 \(sz_i\)，则有 \(v(P)=\text{lcm}(sz_i)\)。原式子可以转化为：
\[\sum_{i,j}sz_isz_j\text{lcm}\left(\text{lcm}_{k\neq i,k\neq j}\left(sz_k\right),sz_i+sz_j\right) \]这能做吗注意到 \(\sum sz_i=n\)，所以本质不同的 \(sz_i\) 级别是 \(\mathcal{O}(\sqrt{n})\) 的。考虑枚举 \(sz_i\) 并计算新的 \(\text{lcm}\)。需要维护一个数据结构满足加入一个数，删除一个数，计算所有数的 \(\text{lcm}\)，可以对每个质数维护幂次的前三大值，这样只需要枚举加入和删除元素的所有质因子，所以复杂度是 \(\mathcal{O}(n\omega(n))\) 的。
P8339 [AHOI2022] 钥匙
Description
一棵 \(n\) 个点的树，树上每个结点有一个左括号或者右括号，括号有颜色，只有相同颜色的括号可以匹配。\(q\) 次询问有向路径 \(u\to v\) 上的括号能够匹配的数量。保证同种颜色左括号不超过 \(5\) 个。
Analysis
考虑每个左括号对其它结点的贡献，发现它们只会和特定的括号匹配，并且对于这个左括号，不存在一条路径上同时有和它能够匹配的两个右括号。所以可以找到所有可以匹配的右括号，然后用 HNOI2015 接水果的技巧做二维数点。使用虚树，复杂度 \(\mathcal{O}(n\log n)\)。
Conclusion
不是很困难的题，理清楚却用了比较长时间。比较有启发意义的是利用括号序列刻画原问题，一类特殊的匹配问题，都可以使用括号序列来刻画。
P4751 【模板】"动态DP"&动态树分治（加强版）
Solution
全局平衡二叉树。
全局平衡二叉树是一个类似 LCT 的结构，它对每一条重链建立一棵二叉树，在重链交界处会存在虚边，注意这条虚边同 LCT 一样，认父不认子。每条链的二叉树以带权重心为端点确定左右儿子，权值为 \(u\) 的所有轻子树大小之和 \(+1\)。这样可以发现，无论走重边还是轻边，全局平衡二叉树上的子树大小都至少变为原来的两倍，所以全局平衡二叉树的树高是 \(\mathcal{O}(\log n)\) 的。
使用全局平衡二叉树代替线段树，做和动态 DP 类似的操作即可。
CF938G Shortest Path Queries
Analysis
考虑只有加边，使用经典套路，此时我们需要维护一棵生成树，支持加边、查询两点 \(u,v\) 间异或路径的长度。如果出现环，加入线性基即可。所以只要考虑怎么维护。
考虑可撤销并查集，对于每个点 \(u\) 维护树根 \(f_u\) 的同时，维护 \(d_u\) 表示 \(u\) 到根的异或路径的长度。考虑一个合并操作 \((x,y)\)，将 \(y\) 接到 \(x\) 上面，那么 \(d_u\) 变为 \(d_y\oplus d_u\oplus w\oplus d_x\)，相当于对集合全局异或一个 \(d_y\oplus w\oplus d_x\)，把这个权值挂到并查集的边上，然后查询路径异或和就可以得到 \(d_u\)。
考虑有删边，加上线段树分治即可。
P8334 [ZJOI2022] 深搜
Analysis
套路题，但是好麻烦。
原式子要求 \(\sum P(X=i)i\)，差分变成 \(\sum P(i\leq X)\)，相当于把所有 \(<i\) 的结点全部删掉之后 \(x\to y\) 的概率。
考虑路径概率怎么计算，对于路径上一条边 \(u,v\)，\(u\) 不能走到其它包含已经删除点的子树，假设这类子树个数为 \(c_v\)，答案就是 \(\dfrac{1}{c_v+1}\)，对于路径上的每条边乘上这个系数即可。
考虑求出所有路径，那么设 \(g_u\) 表示 \(u\) 开头的路径的和，\(f_u\) 表示所有路径的和。那么转移式子：
\[g_u=1+\sum_v \dfrac{g_v}{c_v+1},f_u=\sum_v f_v+g_u \]直接 DP 可以得到平方算法。
考虑每个点只会被删掉一次，考虑一个点被删掉之后的影响。首先 \(c_u\) 会变化，这取决于 \(u\) 的兄弟结点有几个结点子树内有删点，将其称为“坏点”，所以我们需要处理删点和坏点的影响，并得到 DP 值。考虑动态 DP。将转移过程中 \(g_v\) 的系数称为 \(coef_v\)，转移矩阵为：
\[\begin{bmatrix}g_h&f_h&1\end{bmatrix}\begin{bmatrix} coef_h&coef_h&0\\ 0&1&0\\ \sum coef_lg_l+1&\sum coef_lg_l+1+\sum f_l&1 \end{bmatrix} \]维护 \(coef_h\) 是简单的，只要维护轻儿子答案即可，唯一的问题是 \(c_l\) 会变化，不过设 \(u\) 下坏点有 \(bad_u\) 个，则 \(c_v\) 只会是 \(bad_u\) 和 \(bad_u+1\) 两种，分别维护两种数 \(g_v\) 的和即可。
P8576 「DTOI-2」星之界
分块就行，但是 MLE。
CF521D Shop
Analysis
尝试做 exchange argument，最后只能放出来一个比较松的限制，没啥用。
不过可以发现加法操作一定是以递减顺序进行的，这意味着执行一次加法操作之前，\(a_i\) 的值是确定的，这同时意味着：一次加法操作可以等价地看做一次倍率为 \(\dfrac{a_i+x}{a_i}\) 的乘法操作，而只有乘法操作的前提下，元素的选择是增量的，容易使用堆维护。
赋值操作的处理比较简单，因为赋值只会在第一次操作出现，所以可以看做一次加法操作。
Conclusion
将加法看做乘法操作之后容易看出增量性质，不同元素之间先后顺序的比较也是显然的，所以关键只在一步：对加法操作的转化，更一般的，是对模型在不影响答案前提下的局部调整。可以在一些特殊情况中得到启发，比如说每种元素只有一个。
另外令人不禁联想到的是，邻项交换背后更为本质的性质实际是：元素关于选择的个数是增量的，有了这个性质我们只需要找到最优排列就好了。
P8330 [ZJOI2022] 众数
Analysis
开始以为只要套用 [SDOI/SXOI2022] 整数序列 就好了，后来做了一下发现自己不会，然后卡了一会才做出来……
先简单转化问题，容易发现原问题等价于：找到两个元素 \(x,y\)，将 \(x\) 标为 \(-1\)，\(y\) 标为 \(1\)，最大化 \(x\) 的个数加上其生成序列的最大子段和。对于颜色考虑根号分治。包含大块容易处理，但是小块之间不好处理，唯一的性质是元素个数 \(\leq B\)。
稍微愣了下，然后想到要考虑小块的所有区间，我们需要做一个类似区间众数的东西，使用数据结构较为难以处理。不过可以发现区间众数不超过 \(B\)，于是可以考虑只存储区间内出现次数不超过 \(B\) 的数即可。将这个想法完善之后可以得到一个类似扫描线的算法：记录 \(f_{i,j}\) 表示 \(i\) 前出现 \(j\) 个相同元素的元素左端点，容易增量维护 \(f\) 数组，查询的时候遍历 \(f\) 数组并更新答案即可。其中涉及到寻找第一个大于 \(x\) 的位置的问题，使用双指针可以直接维护。
由于一些原因，需要正反扫两边。
Conclusion
不是很困难但是反应还是慢了，主要问题在于在应用元素出现次数 \(\leq B\) 这个性质的时候，我尝试寻找关于最优解的性质而不是将它作为缩小规模的优化工具，所以找不到想要的性质时换换思路还是很重要的。
P8365 [LNOI2022] 吃
Analysis
好玩捏。
考虑 \(a_i\geq 2\) 的包，发现加法基本没啥用，加一个最大的直接跑路就完了，进一步容易证明 \(a_i\geq 2\) 的 \(b_i\) 最多只会选一个加，枚举加哪个就好了。
2022.1.31 联考 T3
Description
给定长度为 \(n\) 的序列 \(a\)，\(m\) 次询问区间出现次数第 \(k\) 小的数。
Analysis
想了好久根号分治，其实莫队+值域分块就做完了。
2022.1.31 联考 T2
Description
交互题。有 \(n\) 个人，分为好人、坏人和乐子人。可以提出如下三种询问：
- 你是不是人？好人回答 \(1\)，坏人回答 \(0\)，乐子人随机。
- 集合 \(S\) 有多少个好人，好人回答好人数量，坏人回答坏人和乐子人数量，乐子人随机。
- 集合 \(S\) 有多少个坏人，和上面一样。
求出每个人的身份。保证乐子人不超过 \(n/4\) 个。
Solution
如果没有坏人，那么好人肯定更多，所以只需要找一个众数，然后可以通过每次询问相邻两个人的身份来确定答案。
首先先组合出一个操作：询问集合内的好人数量。因为全集好人肯定更多，所以如果对全集都询问集合内好人数量，那么最后的众数就是正确的答案。
如果我们找到一个好人，问题就解决了。由于好人数量是过半的，所以考虑摩尔投票。具体地，将集合分成两个部分，询问其中一个集合内好人数量是否过半，如果是就继续做，否则去另外一个集合询问。
拓展到有坏人的情况，首先对所有人都问一遍，回答 \(1\) 的是好人和乐子人，回答 \(0\) 的是坏人和乐子人，其中必然有一个乐子人数量不到半数，对这个集合执行上述算法即可。
Conclusion
一般的摩尔投票基于这样一个事实：若存在绝对众数，则将集合划分成任意两个集合，必然有一个集合存在绝对众数。找众数的方法隐含了这个事实：对于两个不同的数，必然不存在绝对众数。
当将问题转向求众数时，我们可以通过摩尔投票法不断缩小集合——在有能力判断一个集合内是否存在绝对众数的前提下。于是问题可以转化为判断一个集合内是否存在绝对众数，一个更强的问题求出现次数。此时我们需要运用已有的性质——好人更多，也就是说更多的询问指向正确的答案，而不会被混淆。
也许是交互题的一个技巧，不过我不太懂交互。
P3228 [HNOI2013]数列
Analysis
不会做。
生成函数刻画：
\[[x^n]\dfrac{1}{1-x}\cdot \dfrac{x}{1-x}\cdot \left(\dfrac{x(1-x^m)}{1-x}\right)^k \]写成组合式子就是：
\[\sum_{i=0}^{k-1}\binom{k-1}{i}(-1)^i\binom{n-im}{k} \]这个式子对我来说过于超前了。
Solution
换一种组合刻画方式，或者说，换一种构造对象的方式。差分后形式化题意：
- \(\sum\limits_{i=1}^k d_i\leq n\)。
- \(\forall i\in[2,k],d_i\leq m\)。
\(d_1\) 是特殊的，如果先构造 \(d_1\)，再构造后面的部分的话，则需要一个容斥，最终会得到上面的式子。考虑先构造后面再构造 \(d_1\)，因为无论怎么构造和都不会超过 \(n\)，所以得到每个序列的贡献：
\[\sum_{d_2,d_3,\cdots d_k}\left(n-\prod_{i=2}^k d_i\right) \]这个式子就很好算了。
Conlusion
题解区有大佬给出了第一个式子的推导方式，非常复杂。
这道题给出的启示就是，对于计数问题，由组合对象转向代数推导的这一部分是尤为重要的，对于不同的转化方式，推导的方法和难度都天差地别，所以代数推导能力固然是重要的，但是从不同角度构造组合对象，给出合理的刻画，也是极为关键的一步。
P6944 [ICPC2018 WF]Gem Island
Analysis
先差分，然后二项式反演意义下可以得到个式子，懒得写了，感觉输出浮点数有点抽象。
Solution
考虑一个 DP。假设最后第 \(i\) 个颜色的个数为 \(c_i\)，容易发现每个 \(c\) 出现的概率是均等的。我们只需要求 \(\sum F(c)\) 即可，其中 \(F(c)\) 表示数组 \(c\) 中前 \(r\) 大的数的和。
考虑一个 DP，关键在于怎么在递推的过程中维护前 \(r\) 大的数的和。可以考虑沿用分拆数 DP 的方法，每次插入若干个 \(0\)，并将之前的序列整体 \(+1\)，这样 \(+1\) 操作对于第 \(r\) 大的贡献就是 \(\min(k,r)\)，\(k\) 为序列长度。
\[f_{i,j}=\sum_{k=1}^{\min(i,j)} \left(f_{k,j-k}+\binom{j-1}{k-1}\min(k,r)\right)\binom{i}{k} \]暴力转移，复杂度 \(\mathcal{O}(n^3)\)。最后的答案就是 \(f_{n,d}/\dbinom{n+d-1}{n-1}+r\)。
Conclusion
在 DP 生成一个序列的方法中，除开最为常规的末尾插入，以分拆数为代表的“插入 \(0\)，全局 \(+1\)”也很常见，考虑 DP 的阶段就相当于考虑对象的生成方法，我们的生成方法需要保证当前对象中能够忽略的信息尽可能多。
P8331 [ZJOI2022] 简单题
Analysis
如果没有题目中的那个性质，直接硬做，可以得到一个怎样的算法呢？路径的形态较为复杂，没有什么能够约束路径的性质，考虑一个 DP，那么问题就是如何构造一条简单路径。“简单”的限制是每个点只能经过一次，那么我们每次往图中加入一个点，并以这个点为中转点更新答案，发现这就是 floyd 算法！于是这个问题能做到 \(\mathcal{O}(n^3)\)。
此时我们掌握的性质已经不能引出更优秀的做法，考虑讨论原题的性质：存在一种给边标赋权的方式，使得任意简单环的权值和都相等。容易发现不同点双之间是独立的，考虑一个点双。稍微手玩一些不合法情况（我手玩的是两个三元环用两条边连起来），猜想一个点双内不可能是三个以上的环套起来。考虑证明，先构造两个环，讨论下一条边怎么加，发现这一条边只能加在两个相交点的位置。于是我们得到了一个更准确的结论：一个点双内部度数超过 \(2\) 的点不超过两个。
于是可以考虑做原问题了，因为点双内部 \(x\to y\) 的路径条数和路径边权和需要一定讨论，我试图寻找更为优秀的结构，但是并没有。
Solution
实际上循序渐进的推导更为管用。考虑暴力怎么做，每次对于一条路径找到路径上的所有点双，暴力求出点双内部的路径数和路径和，并将其与之前的路径合并。一个事实是这个路径是线性变换，所以可以用矩阵刻画。此时问题相当于求路径上所有矩阵的积。然而比较棘手的是，矩阵取值和每个点的后继有关，而后继数可能很多。但是除了 \(\text{lca}\) 处，所有点的后继都是它的父亲，而这个的级别是线性的，所以只需要在 \(\text{lca}\) 处额外做一次运算即可。由于矩阵有逆，所以可以差分。复杂度 \(\mathcal{O}(n\log n)\)。
Conclusion
这题没做出来主要是推完结论之后懒了，感觉后面不是很可做，并且对图论模型比较陌生，所以就没有规范地思考数据结构部分。无论什么问题都要从最基础的暴力入手思考优化。
P8332 [ZJOI2022] 面条
Analysis
暴力拿 \(10\)。矩阵拿 \(15\)。
观察到操作之后必然相邻四个数会相同，把四个数缩一起可以缩小矩阵规模，或许能过 \(500\)。
继续观察。想到可以追踪每个位置的贡献（因为贡献是线性的），那么现在相当于要解决这样一个问题：只有一个位置是非 \(0\) 的，这样任何时候序列都可以分成三个连续段，但是仍然难以优化。我们继续观察贡献的形态，发现如果从问题最初始的定义出发，可以把贡献更新的过程看成“翻折”和“拉伸”，进一步我们甚至可以把翻折去掉，把序列倍长之后就只有拉伸了，我们只需要把多出来的部分映射到原位置就好了。所以问题相当于：\(k\) 次操作后，一条线段 \([(i-1)2^k,i2^k)\)，中包含了多少个模 \(2n\) 余 \(x-1\) 或 \(2n-x\) 的数，这个问题是平凡的。于是我们做到了 \(\mathcal{O}(nq)\)。
然后很有自知之明地点开了题解。
Solution
首先拓展我们最开始的结论，最后的序列是 \(a_1^{2^t}a_2^{2^t}\cdots a_{m}^{2^{t-1}}\) 的形式。只需要在这个序列上讨论答案。
观察一次变换带来的影响，序列会变成 \(a_1-a_m,a_1-a_{m-1},a_2-a_{m-1}\)，容易发现差分数组从 \(d_1,d_2,\cdots d_{m-1}\) 变成了 $-d_{m-1},d_1,-d_{m-2},d_2\cdots $。
不过这个变换仍然是复杂的，难以求出 \(k\) 步之后差分数组的形态，不过仍然可以有一些诸如变换存在循环节之类的直觉，考虑做一步转化：往差分数组后面添加 \(-d_m,-d_{m-1}\cdots -d_1\)，那么一次变换相当于将这个新的长度为 \(2m-2\) 的序列做一次置换，并且置换的形式是优美的，即 \(p_i=2i\bmod(2m-1)\)。这个置换是有循环节的，循环节为 \(r=\delta_{2m-1}(2)\)。至于为什么要添加和为什么要倒着加，我也不知道（虽然倒着加可能仅仅是为了显示循环节的长度）
于是我们暂时只需要讨论 \(r\) 以内的问题，即怎么求出 \(0\sim r-1\) 的答案。我们的问题相当于求出 \(a_1\) 和 \(\sum\limits_{pos_i<x} d_i\)，先讨论后者，考虑一个权值的贡献，它必须要到一个满足 \(pos_i<x\) 的位置才有贡献，而步数为两点坐标之差，可以用 NTT 做差卷积。对于前者，发现 \(a_1=2a_1'+\sum_\limits{pos_i\leq n}d_i\)，求出后者在每个时刻的取值用秦久韶即可。
不过如果置换环长度不大的话，处理贡献可能会比较慢。但是置换环是 \(r\) 因数，所以本质不同的长度是 \(d(r)\) 的，问题不大。
然后回答询问就好了。
Conclusion
其它还是好理解的，主要的难点在于加入符号使得变换变成一个置换的形式，而置换我们是存在研究方法的，在置换上面我们得到了有关循环节的性质，个人觉得最难的地方在于发现循环节的长度为 \(2\) 在模 \(2m-1\) 意义下的阶，即使适当补全置换之后很容易看出来，但是怎么想到补全置换呢？
不过一个更为现实的方法是打表，这个只要求置换环的 \(\text{lcm}\)。
SP687 REPEATS - Repeats
Analysis
重复串可以套用优秀的拆分的做法。原理是重复串掐掉头尾还是重复串。
Solution
在字符串上找周期比较困难，转而考虑重复串的 border，这样只需要找两个重叠的串就好了。建立 SAM，则在同一个 endpos 上找到出现间隔最小的相邻两个串，假设间隔为 \(L\)，则答案是 \(\left\lfloor\dfrac{L+len}{L}\right\rfloor\)。不难使用线段树合并维护出 \(L\)。
标签：记录,sum,路径,Analysis,众数,考虑,周做题,DP From： https://www.cnblogs.com/yllcm/p/17090415.html