A. Kendama Challenge

容斥一下变成每一段长度都 $< K$ 的概率。DP，设 $f(i)$ 表示前 $i$ 个人每一段长度都 $< K$ 且第 $i$ 个人失败的概率，转移可以用前缀和维护，时间复杂度 $O(N+\log P)$，其中 $O(\log P)$ 来源于求逆元。

B. Cat Cut

注意到在最终的 $X$ 中，每个 $S_i$ 的贡献是一个子串，且除了第一个贡献非空的串以外都是前缀；如果第一个贡献非空的串是 $S_1$，则必须是后缀，否则可以是任意子串。

考虑 $f(i,j)$ 表示使用串 $S_i,\ldots,S_n$ 的各一个前缀按顺序拼接的长度为 $j$ 的字典序最小的串。可以发现 $f(i,j)$ 一定是某个串 $T_i$ 的前缀。这是因为，首先 $f(i,j)$ 单调递增，因为我们一定能去掉一个更长的串的后缀，得到一个更短的串；且更短的串不可能在某个位置严格小于更长的串，否则一定可以在其后添加一些字符得到更长的串。注意这个结论只有在前缀的情况下才满足，因为如果能选择任意子串，开头位置可能太靠后，导致无法添加足够的字符。

因此我们 DP 过程中只需要保存 $T_i$，转移时只需要计算 $S_i$ 的一个前缀和 $T_{i+1}$ 的一个前缀拼接起来的最小长度为 $M$ 的串，也就是让这个前缀和 $T_{i+1}$ 直接拼接起来字典序最小。更新答案也是类似的，假设第一个有贡献的串是 $S_i$，则选择的子串的起始位置一定是 $S_i+\infty$ 的字典序最小的后缀，其中 $\infty$ 是一个比其余字符都大的字符；如果是 $S_1$，只需要计算 $S_1+T_{2}$ 字典序最小的长度为 $M$ 的子串，可以用类似最小表示法的方式解决，或者直接 $O(M^2)$ 暴力。

如何计算 $S$ 的一个前缀拼上 $T$ 之后字典序最小的串？我们先找到答案第一个小于 $S$ 的位置，假设是 $S_i$，这就要求 $S[1:i-1]$ 的一个后缀要匹配上 $T$ 的一个前缀，且 $T$ 的下一个字符小于 $S_i$，这很容易用 KMP 判断。此时匹配的一定是 $T$ 的一个前缀的 border，我们要比较的是 $T$ 在去掉前缀的这段 border 之后的字典序。注意到因为是 border，设两个 border 分别是 $X,Y$（$|X|<|Y|$），则要比较的是 $T[|X|+1:]$ 和 $T[|Y|+1:]$ 的大小，而因为 border 的性质，$X$ 是 $Y$ 的后缀，所以也等价于比较 $T$ 和 $T[|Y|-|X|+1:]$ 的大小，这可以用 Z 函数在线性时间内完成。

综上所述，我们在 $O(NM)$ 的时间内解决了这个问题。

C. Partition AND/OR Aggregation

注意到在区间扩张的过程当中，区间 or 是递增的，区间 and 是递减的，因此 $S(B)$ 是递减的。

最大化

问题相当于分成 $M$ 段，并选择 $K$ 段作为关键段，最大化关键段分数的最小值。如果 $K< M$，则答案一定为 $1$，因为我们可以将 $A_1,\ldots,A_K$ 单独分成一段，然后将后缀分成 $M-K$ 段。

如果 $K=M$，那么可以二分答案，每次贪心分尽可能长的段。这里二分可以使用分数二分，或者在所有可能的分数中二分，因为每个左端点只有 $O(\log V)$ 种分数，总共 $O(N\log V)$。

最小化

令 $K\gets M+1-K$，则问题相当于分成 $M$ 段，并选择 $K$ 段作为关键段，最小化关键段分数的最大值。根据单调性，一定存在最优解满足非关键段的长度都为 $1$，我们只需要选择 $K$ 个不相交的段，使得总长度不超过 $N-(M-K)$ 即可。

二分答案，问题变为选择 $K$ 个不相交的关键段，最小化总长度。我们把这个问题看成分成 $K$ 段，每一段的代价是段内最短的关键段长度，可以证明这个代价是 Monge 的。因此我们可以 wqs 二分，二分后内部是 $O(N)$ 的 DP。

时间复杂度 $O(N\log N(\log N+\log V))$。

D. Campaign Speech

答案等于周长减去边界上相邻两个地点的最大距离。要求出每个地点离起点沿某个方向的距离，只需要快速定位每个点所在的边，我们分成水平和竖直两种情况，分别在对应的行或者列二分即可。

时间复杂度 $O((N+M)\log N)$。

E. Ball Dumping Golf

考虑一张 $N$ 个点的有向图，对于盒子 $i$ 中的每个标号为 $j$ 的球，连一条 $i$ 到 $j$ 的边。则图中每个连通块都有欧拉回路，欧拉回路就对应了一个操作序列，因此得分就等于图中的连通块数量。

设 $f_n$ 表示 $n$ 个点的所有方案数，则 $\frac{(nM)!}{(M!)^n}$，我们对其 EGF 求 $\ln$ 就能得到连通图的方案数，然后再用连通图乘上任意图就得到了所有方案的连通块数的总和。

时间复杂度 $O(NM+N\log N)$。

F. 1e16 Cities

设两个数为 $gx$ 和 $gy$，其中 $\gcd(x,y)=1$，则有边的条件相当于 $g(xy-A)=B$。容易发现这样的边数并不多，我们可以枚举 $g$，再枚举 $x$ 得到 $y$，总的边数不会超过 $D^2$，其中 $D$ 为 $A+B$ 范围内的约数个数最大值，大约在 $10^3$ 级别。实际上这是一个比较松的上界，很难取满。

找到所有边之后 BFS 预处理即可回答询问。注意这个图只有 $10^{16}$ 个点，而我们找到的数对可能超过这个范围。

G. The Symbolic Tree

显然答案是关于 $K$ 的 $N-1$ 次多项式，DP 求出 $K=0,\ldots,N-1$ 的答案后插值即可，时间复杂度 $O(N^2)$。

H. How to Validate Such a Program

令 $D$ 是集合中的点的距离矩阵，则询问的结果相当于 $\operatorname{tr}(D^k)$。我们可以利用这些结果计算出 $\det D$。

具体地，令 $\lambda_1,\ldots,\lambda_n$ 是 $D$ 的所有特征值（记重数），则 $\operatorname{tr}(D^k)=\sum_{i=1}^n\lambda_i^k=p_k$。而 $\det D=\prod_{i=1}^n \lambda _i$。令 $e_k$ 表示 $\lambda_1,\ldots,\lambda_n$ 的第 $k$ 个基本对称多项式，即任选其中 $k$ 个的乘积之和。

由牛顿恒等式可以得到 $$ ke_k=\sum_{i=1}^k(-1)^{i-1}e_{k-i}p_i $$ 从而可以 $O(n^2)$ 递推得到 $e_n=\det D$。

Graham-Pollak 引理：一棵树的距离矩阵的行列式等于 $(-1)^{n-1}2^{n-2}(n-1)$。

证明可以考虑每次用一个叶子和其父亲做消元。在题解给出的论文中，还提供了一系列的拓展公式，利用这些公式我们可以证明删除一个度数为 $d$ 的点后的距离矩阵的行列式等于 $(-1)^{n-2}2^{n-3}((n+3-d)d-4)$。当 $P$ 足够大时，$d=1$ 的值在模 $P$ 意义下和 $d>1$ 的结果都不一样，所以我们可以通过询问 $|V|\setminus \{v\}$ 来判断 $v$ 是否是叶子。

I. Xor Magic Square

当 $N$ 是偶数时，显然取全 $1$ 矩阵。

当 $N$ 是奇数时，考虑二进制第 $0$ 位，每一行每一列分别至少有一个数是 $0$，因此在二进制的更高位中，每一行每一列至少有两个 $1$。这样我们得到了答案的一个下界是 $N^2+3N$。

先构造一个 $N=5$ 的解，例如：

1 1 1 2 3
2 3 1 1 1
1 1 2 3 1
3 1 1 1 2
1 2 3 1 1

当 $N$ 变大时，只需要在一条对角线上填 $2$，另一条对角线上填 $3$，其余位置填 $1$ 即可。

当 $N=3$ 时，限制条件可以推出 $A_{2,2}=0$，所以无解。

J. Sum of max of iai

考虑计算分数不超过 $m$ 的排列的数量，则要求 $a_i\le \frac{m}{i}$。令 $b_i=\min\left\{N,\left\lfloor\frac{m}{N+1-i}\right\rfloor\right\}$，则答案等于 $\prod_{i=1}^N (b_i-i+1)$。

令上述的数量为 $f(m)$，则答案等于 $N!\cdot N^2-\sum_{m=0}^{N^2-1}f(m)$。在 $m$ 增加的过程中，$b_i$ 只有 $N^2$ 次变化，每次变化后 $O(1)$ 维护乘积即可做到 $O(N^2)$ 时间。一种实现方式是记录每个 $b_i$ 下一次变化的时间，因为间隔不超过 $N$，只需要用一个长度为 $N$ 的数组记录即可，这样空间是 $O(N)$ 的。

K. Square Resistance Value

我们知道串联电阻是求和，并联电阻是调和平均数。那么串联 $1\Omega$ 电阻相当于分子加上分母，并联 $1\Omega$ 电阻相当于分母加上分子，于是我们可以对 $\sqrt D$ 进行连分数近似。根据连分数理论，连分数的任何截断 $\frac{p_n}{q_n}$ 的误差不超过 $\frac{1}{q_n^2}$，因为这是分母不超过 $q_n$ 时的最佳近似。可以验证在本题的数据范围内误差总是不超过 $10^{-6}$。事实上，可以证明渐进意义下假设边数是 $M$，则误差不会超过 $D^{-\Theta\left(\frac{M}{\sqrt D}\right)}$。

L. Make Many KUPC

令 $T={\tt KUPC}$。从后往前贪心，维护当前选上的四种字符的数量。如果当前的字符是 $T_i$，当 $i=4$ 或者 $T_{i}$ 的数量小于 $T_{i+1}$ 的数量时我们就选上当前的字符。最后我们把选择的第 $i$ 个 K、U、P、C 分成一组。正确性可以用交换论证来证明。时间复杂度 $O(N)$。

M. Linked VERSE

给定 $c$ 之后，最终的 $x$ 就等于将 $-1$ 替换成 $-c$ 之后的最大后缀和，所以过程中 $x$ 的最大值也就是最大子段和。考虑先预处理出凸包，其中点的横坐标是子段中 $-1$ 的个数，纵坐标是非负数的总和。可以考虑分治，那么分治中心往左往右分别都只有凸包上的点有用，合并只需要闵可夫斯基和。这样我们找到了 $O(N\log N)$ 个可能有用的点（实际上是 $O(N)$ 个，因为对于固定的 $-1$ 的个数，只需要保留最大的总和），对其建凸包，每次询问只需在凸包上二分。时间复杂度 $O((N+Q)\log N)$。

N. Cellular Component Constellation

首先，因为至少有 $M$ 种不同的连通块大小，所以每种颜色的格子数量至少是 $\frac{M(M+1)}{2}$，总和是 $M(M+1)$。所以当 $M\ge N$ 时一定无解。

当 $M < N$ 时，首先考虑构造一个 $M\times(M+1)$ 的子矩形，其中每种颜色大小为 $1,\ldots,M$ 的连通块各出现一次。$M=6,7$ 的例子如下：

.#.#.#
##.#..
...###
###...
..#.##
#.#.#.
#.#.#.

.#.#.#.#
##.#.#..
...#.###
####....
....####
###.#...
..#.#.##

构造的思路是从一个角落开始可以得到大小为 $1,3,5,\ldots$ 且颜色交替的连通块，将其对称且取反后可以得到所有奇数大小的连通块。再对称一次，并且将边界调整一格，就能得到所有偶数大小的连通块。

得到这个 $M\times (M+1)$ 子矩形后，剩下的部分用棋盘染色即可。注意边界上会有连续两个相同颜色的格子，我们将它视为一个整体进行棋盘染色，这样额外的格子的连通块大小不会超过 $2$，且 $M=1$ 时相当于直接棋盘染色。

O. Xor Triangle

注意到 $x,y,x\oplus y$ 这三个数已经满足退化形式的三角形不等式，即 $a+b\ge c$，所以只需要让其不取等即可。我们用总的方案数减去取等的方案数。总的方案数为 $4^{N}$；如果 $a=b+c$，方案数为 $3^N$，所以减去 $3^{N+1}$；如果其中一个数为 $0$，则算了两次，所以再加上 $3\cdot 2^N$；最后再减去全 $0$ 的情况。

因此总的方案数为 $4^N-3^{N+1}+3\cdot 2^N-1$。