为什么 Edu G 题好多字符串啊？
A
按照题意模拟即可。（可以借鉴一下玩几何冲刺的感想）
B
一开始看错题了，以为每次只能取一个区间。。题目是每次可以取一个子序列。
那么我们就从大到小排序，贪心尽量选择多的数，选到最后一个能让平均值 $\geq x$ 的值即可。
子区间版本我还不会，有谁会可以教教我。
C
只有一个位置不会被爆炸伤害，枚举这个位置就可以了。如果一个位置被爆炸伤害需要的费用就是 $\max\{0,a_i-b_{i-1}\}$，否则就是 $a_i$。
D
打表找规律发现序列形如 $1,2,1,3,1,4,\ldots,2,3,2,4,\ldots\ldots,n-1,n$，然后就可以做了，定位到第一个点的位置然后暴力循环即可。
比如 $n=3$ 的序列就是 1 2 1 3 2 3，$n=4$ 的序列就是 1 2 1 3 1 4 2 3 2 4 3 4。
E
首先如果 $a|b$ 那么最短路一定是 $d(b)-d(a)$（每次随便选一个 $p$ 乘上去就行）
其他情况我们的路径肯定是先单调除/乘一个数，再单调乘/除一个数，不会出现交替的情况（因为这样会多加一个数的 $d$），所以我们现在就是要考虑选择 $\gcd(a,b)$ 还是 $\text{lcm}(a,b)$ 中转。
我们断言使用 $\gcd(a,b)$ 中转最优，然后我们就可以分别算出 $a \to \gcd(a,b)$ 和 $\gcd(a,b) \to b$ 的路径条数，直接相乘就好了。
接下来我们考虑如何算出 $a \to \gcd(a,b)$，设一个数唯一分解后的形式是 $a=\prod_{i} p_i^{e_i},\gcd(a,b) = \prod_{i} {p'}_i^{{e'}_i}$，可以设 $\Delta_i = e_i-e'_i$，答案相当于有 $\sum \Delta_i$ 个数，第 $i$ 类有 $\Delta_i$ 个，相同类别的数之间不可区分，问路径方案数这样一个组合问题，也就是多重集排列组合。
一个不知道对不对的乱写的证明
首先最优一定是中间不拐弯的一种走法（先一直除再一直乘），设 $g = \gcd(x,y),l = \text{lcm}(x,y)$，我们只需要证明 $x \to g \to y$ 比 $x \to l \to y$ 优就好了。
也就是要证明：
$$ \begin{aligned} d(x)-d(g)+d(y)-d(g) &\leq d(l)-d(x)+d(l)-d(y)\\ d(x)+d(y) &\leq d(l)+d(g) \end{aligned} $$
考虑 $\gcd,\text{lcm}$ 和因数个数 $d$ 的本质定义，实际上是要证明
$$ \prod_{i=1}^m a_i + \prod_{i=1}^m b_i \leq \prod_{i=1}^m \max\{a_i,b_i\}+\prod_{i=1}^m \min\{a,b\} $$
其中 $\forall i,a_i,b_i \geq 1$。
考虑使用数学归纳法：$m=1$ 时显然成立（$a+b \leq a+b$），现在我们先证明 $m=2$ 成立：
不失一般性我们设 $a_1 \leq b_1$，接着分类讨论：
- 如果 $a_2 \leq b_2$：式子变成了 $a_1a_2+b_1b_2 \leq b_1b_2+a_1a_2$，显然成立；
- 如果 $a_2 > b_2$：式子变成了 $a_1a_2+b_1b_2 \leq b_1a_2+a_1b_2$，发现这是一个排序不等式的形式（$a_1 \leq b_1,b_2 < a_2$ 是排好序的，所以 $a_1b_2+b_1a_2 \geq a_1a_2+b_1b_2$）；
附：排序不等式维基页面
考虑对于 $m > 2$，我们使用数学归纳法，设 $A=\prod_{i=1}^{m-1} a_i,B = \prod_{i=1}^{m-1} b_i,C = \prod_{i=1}^{m-1} \max\{a_i,b_i\},D=\prod_{i=1}^{m-1} \min\{a,b\}$，那么有 $A+B \leq C+D$，我们现在要证明 $Aa_i+Bb_i \leq C\max\{a_i,b_i\}+D\min\{a_i,b_i\}$，只需要注意到 $C \geq \max\{A,B\},D \leq \min\{A,B\}$ 即可类似上面讨论证明。
F
这种匹配的题都可以设 $f_{i,j}$ 表示考虑了 $a$ 串前 $i$ 个和 $b$ 串前 $j$ 个的最小代价，于是有转移：
$$ \begin{aligned} f_{i,j} \to \begin{cases} f_{i+1,j}+p_{i+1},\\ f_{i+1,j},& a[i+1] \leq b_{i+1}\\ f_{i+1,j+1}+p_{i+1}, &a_{i+1} = b_{i+1}\\ \end{cases} \end{aligned} $$
考虑用线段树维护第二维，注意到第三种操作只会修改一个位置即可。（事实上可以写树状数组）
最后是需要一个一个后缀加，单点查询的数据结构，取最大值讨论一下 $p$ 的正负就行了。
G
首先介绍一下字符串匹配的 FFT 做法：
设文本串为 $s$，模式串为 $t$，我们可以设两个位置的匹配函数 $c(i,j) = (s_i-t_j)^2$，于是 $s$ 以 $x$ 开头的一段字符串是否和 $t$ 匹配就是 $f_x = \sum_{i=1}^m c(x+i-1,i)$ 是否为 $0$，拆开后发现是一个卷积的形式，直接做就行了。
对于这个题我们可以发现匹配函数是 $c(i,j) = (s_i-t_j)^2(s_{p_i}-t_j)^2$，也直接做就行了。
注意到我们如果是 $\bmod 998244353$ 等价于在这个质数下取模，但这显然不够会被卡，我们可以有一下解决方案：
- 多模数
- 每个字符随机权值
- 随机模数
感觉 $2$ 比较好。。也不用多背几个 NTT 模数。
