2022 HDU 多校 1
A String
开始考虑 KMP 直接做发现相交和模 $k$ 两个条件都难以递推，所求式子也看不出除了直接求 $F$ 外的处理手段。
后来考虑 Z 算法，如果能够求出 Z 数组，即每个后缀和开头的 LCP ，就一定确定了交的起点。
而且，当交的起点固定，每当 border 长度加一，交的大小一定正好增加 $1$ 。同时，border 长度的上限其实就是 Z 数组的值。
因此相当于给定了一个区间，给里面的元素从某个元素开始每隔 $k$ 加一。直接前缀和处理即可。
题解提到也可以用 KMP 解决。
如果通过 KMP 的 next 关系建树，对一个点有贡献的 border 一定是这个点向上的一条链上的满足一个同余关系的点。
这个链的链顶是可以在预处理的时候得到的，维护每个前缀不超过一半的最长 border 即可（NOI 动物园）。
所以 DFS 的时候同时对于每个 $i$ 维护链中的 $2u \equiv i \pmod k$ 的 $u$ 的个数即可。向下 DFS 的时候只会从链中弹出链顶的一些值和加入一个值。
B Dragon slayer
$2^k$ 枚举墙的出现状态。由于 $n,m \le 15$ 直接从起点 DFS 看是否可以到达终点即可。
对于每个墙相当于在网格图上断掉若干条边。
C Backpack
直接 dp 是 $O(nmw)$ 的，大概 $2^{30}$ 。
可以发现 $dp[w][i] \to dp[w\oplus w_i][i+v_i]$ 中第二维可以直接用 Bitset Or 操作实现。复杂度 $O(\frac{nmw}{\omega})$ ，就可以跑过去了。
D Ball
直接考虑枚举两个点作为中位数，它们的距离 $d$ 必须是个质数。然后第三个点必须满足到一个点的距离小于等于 $d$ ，到另一个点的距离大于等于 $d$ （暂时不考虑相等时的重复计算）。
曼哈顿距离中小于等于 $d$ 不太容易表示，考虑通过 $X=x-y,Y=x+y$ 的坐标变换变成切比雪夫距离。
然后相当于有两个通过枚举的点确定的正方形，它们的交是一个长方形，需要求出两个正方形除去交的部分的点的个数。
由于不同的坐标个数只有 $O(n)$ 种，所以可以离散化后利用二维前缀和分别计算正方形和长方形内点的个数。复杂度 $O(n^2\log n)$ 或 $O(n^2)$ 。
然后考虑算重的部分。会发现，如果在容斥计算时把边界的点全部考虑上，画图可以发现：
- 与一个点距离为 $d$ ，与另一个点距离大于 $d$ 的点会被计算 $2$ 次。
- 与一个点距离为 $d$ ，与另一个点距离小于等于 $d$ 的点会被计算 $0$ 次。
所以在去掉交的矩形时（即减去两倍矩形中点得个数时），可以选择减一次矩形内的点再减一次不含边界的点，这样就可以保证两者都会被算重恰好一次。
然后考虑去重，即需要找出多少个三元组，满足其中有两个距离相等。这个可以枚举一个点，对每对与它距离相同的两个点计数一次，即 $\binom n 2$ ，其中 $n$ 为与它的距离等于某定值 $t$ 的点的数量。
然后考虑三个距离都相同的情况。这种情况会被计算 $3$ 次并扣掉 $3$ 次，最终被计算了 $0$ 次。所以需要加上这种情况的个数。
可以发现，如果三个距离相同，距离一定是偶数，所以一定是 $2$ 。所以很容易地判一下即可。
直接做复杂度是 $O(n^2\log n)$ ，由于值域很小，离散化后对应到离散化数组的过程可以不用二分，直接预处理即可，复杂度就是 $O(n^2)$ 。
但是官方题解直接 $O(\frac {n^3}{w})$ 爆过去了。。所以为啥不开 $n = 1000$ ，$n = 2000$ 还给 $10$ 组数据让人不敢 bitset 啊！
E Grammar
考虑预处理出所有不会进入循环的点的长度，如果大于 $10^{18}$ 则取 $\min$ 。
然后考虑递归寻找 $x$ 串中的第 $c$ 个位置。首先对于没进入循环的部分可以直接做，对于进入循环的部分，我们暴力递归下去，并记录第一次到每个节点时的 $c$ 的值。
当我们第二次到达同一个节点时（进入循环），可以发现串的循环节的长度是第一次到达该点和第二次到达该点的 $c$ 之差。直接给 $c$ 模这个差后继续暴力即可。
复杂度 $O(nq+n^2)$ 。
不太明白题解在二分什么，明明直接暴力 dfs 复杂度就挺对（？）
F Travel plan
如果存在两个相交的环，拼起来后除去公共部分一定是个偶环，因此所有环不相交，原图是个仙人掌。
考虑 $\gcd = k$ 的限制，稍微反演一下得到
所以只需要求出路径上所有边都被 $T$ 整除的路径数量即可。直接暴力枚举每个 $T$ 对应的边来构图总边数也不会超过 $O(m\max d(L))$ ，看起来是可以通过的。
考虑建出圆方树，然后在圆方树上 dp 计算路径数量。对每个节点我们记录这个节点向下的路径数量，并把子树之间的这个值乘起来得到真正的路径数量。注意在方点时，无论是以当前点作为 $\text{LCA}$ 得到的路径数量还是这个点向下的路径数量都需要乘 $2$ ，因为环上点之间的路径总是有两条。
最后直接枚举每个数的倍数反演回去即可。
复杂度 $O(m \max d(L) + L\log L)$ 。过样例后只 TL 了一发，开个快读就过了。和题解做法一样。
G Treasure
建出 Kruskal 重构树后，可以发现查询可以倍增跳完后查子树内不同属性的最大值的和。
维护方法应该比较多样，由于每个属性出现次数不超过 $10$ ，可以考虑把这些点和相互的 LCA 存下来并把虚树的父亲关系建立出来，并对每条链按子树内的最大值来更新。
每次修改操作由于虚树的深度不超过 $10$ ，直接暴力向上跳并且修改对应的链即可。
这个修改差分后就是单点改子树查询，可以直接用 BIT 维护。
复杂度 $O(10(q+n)\log n)$ 。好像和题解做法一样。
H Path
题面写的不太行，很难读懂。最后弄明白意思是走过一次特殊边后如果不走边直接传送，代价为 $0$ ，否则为下一条边边权减去 $K$ 。
到达同一个点有两种状态：从一个特殊边到达和从一个非特殊边到达。总共有 $2n$ 个状态，考虑在这些状态上跑 dijkstra 。
从非特殊边到达一个点 $u$ 时直接 dijkstra 即可。否则，我们可以枚举所有其他点 $1 \le v \le n$ 。如果 $u,v$ 间没有边，那么 $v$ 一定会入队并放到队首，因为两者距离是相同的。如果 $u,v$ 间有边，那么直接按距离为 $w_i - K$ 处理即可。
可以发现如果我们对所有通过第二种方式放到队列里的点在下次考虑这个过程时都忽略掉，那么复杂度就对了。因为相当于每次通过特殊边到达一个点后，每次枚举都要么会把剩余点数减一，要么枚举的是两点间存在边的情况。所以总共的枚举次数是 $O(n+m)$ 的。
可以用 map 或者 hash 判断两点间是否有边。复杂度 $O((n+m)\log^2 (n+m))$ 或 $O((n+m)\log (n+m))$ 。
I Laser
可以先任意找一个点，看看这个点作为中心能不能杀死所有敌人。
如果不行，炸出杀不死的任意一个。
然后这两个肯定处在四条线中不同的线上，枚举一下这两个分别处在什么线上，求出交点判一下即可。
复杂度 $O(n)$ 。
J Walk
如果每次只能走到 $y$ 更小的坐标（即 $S(S(S(y))) = 0$ ），那么问题可以很容易地解决。考虑只要确定了每个 $y$ 坐标出现的次数就能唯一确定走的路径，所以只需要求 $\prod_i \frac{1}{1-f(y_i)x}$ 即可。
由于 $0 \le S(S(S(y))) \le 2$ ，所以有些纵坐标可以被重复经过，因此上面的方法无法奏效。但是如果我们容斥一下，限制就会变成选择若干个 $y’ > y + S(S(S(y)))$ 这种限制。而这个限制中很显然 $y$ 坐标是单调递增的，因此不会重复出现 $y$ 坐标。
所以对于容斥钦定违反限制的一段区间，可以使用之前的思路，对于所有选择 $y$ 坐标的方案求 $f(y_i)$ 的积。因为确定了选择 $y$ 坐标的方案就唯一确定了路径，而选择的最小的 $y$ 就是区间前面的一个无限制的位置。
因此现在问题是，选出若干个 $y$ 坐标，并且相邻坐标之间必须间隔至少 $S(S(S(y)))$ 的值。很明显有 $dp$ 解法以及 GF 的形式：
这个递推很显然可以用矩乘优化，而取决于 $t$ 有三种不同的矩阵。我们可以把所有位置的转移都看成 $3 \times 3$ 的矩阵并乘起来。
在算出 $F[m]$ 后，相当于需要选择一些段拼起来，但是不应该有空段，所以答案应该是
直接多项式求逆即可。
由于矩阵乘法时得到的最长多项式长度显然不超过两边最长长度加起来，可以类似于分治 NTT 来做分治矩阵乘。复杂度为 $O(3^3n\log^2 n)$ ，可以通过（而且无优化的情况下是 QOJ 最快的）。
K Random
显然每个数的期望一直都是 $\frac 1 2$ 。输出 $\frac{n-m}{2}$ 。
L Alice and Bob
如果有两个 $1$ ，分在两边就获胜了。
否则，如果有两个 $x$ ，可以通过分在两边得到一个 $x-1$ 。进而可以发现，拥有两个 $x$ 和拥有一个 $x-1$ 其实是等价的，因为可以把两个 $x$ 捆绑在一起，直到它作为最小值了。
所以从后向前扫一遍，让两两相同的数合并起来即可。（看起来不是很严谨）
复杂度 $O(n)$ 。
题解解释：
把 $i$ 视作 $2^{n-i}$ ，那么 Alice 只需要让黑板上出现 $2^n$ 。同时，每次操作相当于 Bob 让这个集合内的所有数乘二，然后删除另一个集合。
而如果集合中的和大于 $2^n$ ，那么一定能分成两个部分，使得每个集合的和都大于等于 $2^{n-1}$ 。因为不存在 $2^n$ 这个数，所以总可以通过调整小于 $2^n$ 的数来做到。这样就递归到了子问题。
故直接判断和是否大于 $2^n$ 即可，和前面的结果相同。