260625 - 260707
260625 A
由于操作是可逆的，所以可以看成是我们既可以对原序列操作，也可以对目标序列操作，这样我们不难得到一个至多 \(n\) 次操作的构造。在所有前缀和模 \(3\) 相等的位置划分成若干段，也不难说明在段之间操作是不优的，因为至少要操作 \(2\) 次，两个段最多各减 \(1\) 次。问题就转化为判断一个段能否在 \(len-1\) 次操作内做完。考虑 dp，上面操作两个序列的结构本质上是一个只关心相邻操作先后顺序的拓扑序，分析一下可知从左往右依次决定每个位置操作哪个序列，和原问题是等价的，因此直接 dp 即可。
260625 B
一个人的策略实际上是，假设自己是红眼睛，若所有局面的最长时间 \(\max f_S\) 之内还没有人自爆，那他就会在下一天自爆，因此一个局面的时长 \(f_S=1+\min_{x\in S}\max_{S/\{x\}\oplus N(x)}\)，其中 \(N(x)\) 表示 \(x\) 看不到的人构成的集合，\(\oplus\) 表示任意改变集合内的点。将这个转移看成一个博弈过程，容易分析到一个结论，如果 \(S\) 中的某些点可以走到环上，\(f_S\) 就是发散的。所以我们事先删除所有能到环上的点，由此形成一个 DAG。
对着博弈的过程分析，其实容易发现 \(f_S\) 等于 \(S\) 能到达的点的数量，因此第一问简单拆贡献即可。考虑如何判定一个人会不会自爆，他会自爆当且仅当 \(f_S\) 在 \(x\) 处取到最小值，也就是选择 \(x\) 是先手的最优策略之一，也就是顶层节点。因此第二问也可以简单计算。
P13273 [NOI2025] 数字树
考虑从一个合法的方案开始调整，操作形如把一个子树对应的区间 reverse，这样跟原问题等价并且形式更好。如果我们 reverse 了两个完全相同的区间那显然是没问题的，如果我们 reverse 了序列的一段 A（A 代表一个子串），又 reverse 了一个 A()（拼接一些内部匹配的序列），那显然也是没问题的；又发现完美匹配的序列可以夹到 A 中间。这启发我们考察子树内出现次数为奇数的数字的集合 \(S_u\)。两个 \(S_u=S_v\) 的点可以同时交换。
猜测上面的过程是必要的，将节点按照 \(S_u\) 划分等价类，每个等价类形如两组互相包含的区间。考虑一个翻转了奇数棵子树的等价类，不妨设它对应的集合是最大的，那么集合更小的区间无法交换它的第一个和最后一个元素，因此不行。当然空集随便交换。
一个集合大小为 \(1\) 的等价类提供 \(sz-2\) 的贡献，集合大小 \(\ge 2\) 的等价类提供 \(sz-1\) 的贡献，空集提供 \(sz-(2n-2i)\) 的贡献，所以答案就是 \(2^{2n+i-cnt}\) 其中 \(cnt\) 表示等价类数量。考虑如何维护每时刻的等价类数量，为每个点维护一个数组表示每个时刻子树内新加入了哪些数字，那么两个点在时刻 \(t\) 处于同一等价类当且仅当二者数组的前 \(t\) 项相等。用线段树合并维护，可以通过线段树上二分比较两个数组的字典序，于是按字典序排序，再按顺序求一遍相邻点的 \(\operatorname{lcp}\) 即可。复杂度 \(O(n\log^2 n)\)。
AT_agc028_e [AGC028E] High Elements
考虑逐位试填，对于还没确定的后缀，考虑全局前缀最大值在两个子序列中的分布，对于两个子序列中不属于前缀最大值的数，可以免费的将它删掉。因此至少有一个子序列在后缀中只包含全局前缀最大值。然后，如果另一个序列中至少包含一个不属于前缀最大值的数，那就可以将两序列长度的差平滑的调整到下界。所以问题转化为使得两序列的长度之差尽可能大，对第二个序列进行 dp，发现选择一个前缀最大值贡献为 \(2\)，否则贡献为 \(1\)，使用线段树优化即可，这样支持删除最后一个数。两序列都只包含全局前缀最大值的情况显然是平凡的。
AT_arc160_f [ARC160F] Count Sorted Arrays
枚举一个阈值并对序列进行 0/1 染色，显然一个排列会被排好的充要条件是所有阈值对应的 0/1 序列都被排好，如果已知所有 0/1 序列的排序结果，显然可以 \(O(n2^n)\) dp 求出排列数量。考虑说明 \(m\) 次操作中只有不太多的操作会本质改变至少一个 0/1 序列。其实可以通过手玩得知，如果一次操作将某些无效操作变为了有效操作，那么至少有一个有效操作变为了无效操作，因此这么做复杂度是 \(O(n^32^n)\) 的。
P10612 [BalticOI 2001] Box of Mirrors
考虑一个必要条件是所有目的地都在出发地的右上方，猜它是充分的，考虑归纳，若第一行贯穿则直接删除，否则在反射点下放一面镜子，先把已经贯穿的列都删掉，发现在第一行的第一个镜子右面放满镜子是对的。
AT_agc040_f [AGC040F] Two Pieces
看成是对直线 \(y=x\) 上方的部分进行路径计数，任意时刻可以向右瞬移到直线上，单步不能走到直线上。考虑去掉瞬移操作之后形成的路径，在一个点插入瞬移操作形如过该点画了一条斜率为 \(1\) 的直线，上面的部分不能与直线相交于任何一点，因此对于一个截距有且仅有一个位置可以放置该直线，方案数是选一些位置操作，就是一个格路计数乘一个组合数。
qoj5367 递增树列
注意到 \(\operatorname{lca}(p_i,p_{i+1})\) 形成一条根链，对这个根链从下往上 dp，设状态 \(f_{u,i}\) 表示 \(u\) 子树内已经选了 \(i\) 个点的方案数，转移形如从一个儿子走上来，然后在子树内走一走，不能连续走两个相同子树的点。考虑对此限制容斥，变为钦定一些连续段，方案数是阶乘。转移需要枚举两维，复杂度 \(O(n^4)\)。
AT_agc012_f [AGC012F] Prefix Median
看我洛谷题解。
P9535 [YsOI2023] 连通图计数
对于树，\(a_i=deg_i\)，使用 Prufer 序列即可。对于基环树，考虑其圆方树，一个圆点的 \(a_i=deg_i\)，方点的度数可以算出来，使用 Prufer 序列再乘以圆排列即可。对于两个环的图，如果两个环相互分离，那么用上面的方法即可，需要去掉算错的情况；如果形如一个环之间连一条链，环的大小可以算出来，直接用上面的方法再乘以形成这样的点双的方案数即可，需要枚举一条链的长度。
P4831 Scarlet loves WenHuaKe
枚举有 \(2t\) 列有一个炮，所以答案就是
可以卷积求出，复杂度 \(O(n\log n)\)。
P8322 『JROI-4』少女幻葬
考虑分部转移，先从状态 \((d,p)\) 表示 \(\gcd(a_i,a_{i-1})=d,~a_i=p\) 转移到 \((p,t)\) 表示 \(\gcd(a_i,a_{i+1})=t\)，其中需要满足 \(t\perp d,~t\mid p\)，充要条件是 \(t\) 整除 \(p\) 去掉 \(d\) 的所有质因子之后的数，后者可以预处理，随后只需要对 \(p\) 的所有因数做高维后缀和，复杂度 \(\sum_{p}d(p)\omega(p)=O(\frac{n\log^2n}{\log\log n})\)，实际上更低。
然后从 \((p,t)\) 转移到新的 \((t,p')\)，其中需要满足 \(\gcd(p',p)=t\)，考虑莫反，先 \(p,p'\gets \frac{p}{t},\frac{p'}{t}\)，然后相当于枚举 \(x\mid p\wedge x\mid p'\)，贡献 \(\mu(x)\)，可以通过一次高维后缀和，一次对应位置相乘和高维前缀和解决，时间复杂度 \(O(n\log n\log\log n)\)。
CF251E Tree and Table
如果某个位置 \(i\) 满足 \([(i,0)\to (i+1,0)]+[(i,1)\to (i+1,1)]=1\) 就在这里划分，形成若干段，每个段只能是工字形或者其他退化情形，分类讨论即可。