D. Split Plus K
记最后相同的数为 $t$，则不难发现对于每个数 $x$，操作都形如 $t+y=x+k$，直到这个数变成 $t$，若这个数的操作次数为 $y$，则有 $(y+1)t=x+yk$，整理得 $x-t=y(t-k)$，其中 $y\ge 0$，将其改写为 $x-k=y(t-k)$，其中 $y\gt 0$，这样不难发现最优解时 $t-k$ 为所有 $x-t$ 的 $\gcd$，且所有 $t-k$ 同号。
E. Multiple Lamps
既然按下所有按钮，最终只会有编号为完全平方数的灯亮，所以可以数据分治。
-
$n\ge 20$ 全部点亮
-
$n\lt 20$ 注意每一种最终的点亮情况可以反演出按钮情况，所以可以枚举最终亮的灯。
F1. Small Permutation Problem (Easy Version)
$a_1 \gt 1$ 或 $a_n \lt n$ 时无解，启发我们注意到差分只存在 $0,1,2$ 三种，开始分讨 $\Delta=a_i-a_i-1$，并记 $i-a_i=t$。
-
$\Delta=0$：前 $i-1$ 个数不存在 $i$，而且 $p_i\gt i$。
-
$\Delta=1$：前 $i-1$ 个数存在一个 $i$，且 $p_i\gt i$，或者前 $i$ 个数不存在 $i$，且 $p_i\le i$。
-
$\Delta=2$：前 $i-1$ 个数存在一个 $i$，且 $p_i\le i$。
具体计算对答案贡献时，为避免算重，可以对于每个数只在被确定放入到某个位置时统计答案。三种情况的贡献分别是答案乘上 $1,t+t+1,t^2$。
F2. Small Permutation Problem (Hard Version)
有了 F1 的思路，F2 非常简单。
将 $a$ 补充一个 $a_0=0$，且若有解就一定 $a_n=n$。将 $a$ 只保留非 $-1$ 的部分。仍然考虑相邻项 $(x,a_x),(y,a_y)$ 之间的差 $\Delta=a_y-a_x$。发现 $\Delta$ 由两部分构成，$1\le i \le x,x\lt p_i\le y$ 和 $x\lt i \le y,p_i\le y$。于是枚举其中一项的数量即可。
G. Pumping Lemma
三元组 $(x,y,z)$ 同时有前缀和后缀的要求，非常难以枚举。考虑化简一部分。关键转化是只保留 $s$ 与 $t$ 后缀相同的一段后缀，而前面部分一定被 $x$ 包含。删除 $s$ 和 $t$ 的这部分前缀后，$s$ 就成为了 $t$ 的后缀，那么三元组中的 $x$ 就一定是 $y$ 的后缀，于是 $x+y$ 具有周期 $\lvert y\rvert$。这样我们枚举 $\lvert y\rvert \mid \lvert m\rvert - \lvert n\rvert$，再考虑计算 $y$ 的滑动范围即可。
