A. An Easy Geometry Problem
令 $A_i'=A_i-i\cdot \frac{k}{2}$，则对于 $i$，$r$ 是好的半径当且仅当 $A'_{i+r}-A'_{i-r}=b$。
用线段树或树状数组维护正反两个方向的哈希值，询问时二分长度然后比较哈希值即可。
时间复杂度 $O(n+q\log^2n)$。
B. Counting Multisets
考虑 $p(S)$ 是奇数的条件，设 $\mathrm{cnt}(x)$ 是 $x$ 在 $S$ 中的出现次数，则 $p(S)=\frac{n!}{\prod_x \mathrm{cnt}(x)!}$。根据 Lucas 定理，$p(S)$ 是奇数当且仅当所有 $\mathrm{cnt}(x)$ 在二进制下相加没有进位。因此，合法的可重集就是对于 $n$ 的二进制中每个 $2^i$，任意选择一个 $x$ 重复 $2^i$ 次。
现在还要解决 $\mathrm{OR}_{x\in S}x=y$ 的条件。可以通过容斥将条件改写为 $\forall x\in S,\mathrm{bin}(x)\subset \mathrm{bin}(y)$（$x$ 的二进制中的 $1$ 是 $y$ 的子集）。
因此，对于固定的 $y$，只需要计算对于每个 $2^i\in \mathrm{bin}(n),2^j\in \mathrm{bin}(y)$，可以选或不选 $2^{i+j}$，总和等于 $x$ 的方案数。这可以通过数位 DP 解决，即 $f(i,j)$ 表示确定最低 $i$ 位，目前进位为 $j$ 的方案数，时间复杂度 $O(\log x\log n\cdot \mathrm{pcnt}(y))$。
总时间复杂度 $O(2^{\mathrm{pcnt}(y)}\mathrm{pcnt}(y)\log x\log n)$。
C. Counting Strings
（复读官方题解）
首先把条件改写成 $\gcd(r,r-l)=1$。建出 SAM，对于每个 $r-l$，假设保留所有 $\gcd(r,r-l)=1$ 的 $r$ 对应的结点，这样的串的个数就是这些结点到根的路径的并中深度为 $r-l$ 的点数。如果我们把这些结点按 DFS 序排序，则容易维护这些路径的并。
考虑通过搜索枚举 $r-l$ 包含质因子的集合来优化这个算法。在加入一个素数 $p$ 时，要删除所有 $p\mid r$ 的 $r$ 对应的结点，这样的删除对路径并的变化是删除一条链，可以用链表维护前驱后继，求两次 LCA 就能找到这条路径。回溯时撤销修改即可。为了统计答案，我们维护每个深度的点数，修改的影响是区间加，查询是单点求值，可以用 $O(1)$ 修改 $O(\sqrt n)$ 查询的分块维护。
接下来只需要分析这样搜索时需要修改的次数 $F(n)$。实测在 $n=10^5$ 时，修改的次数不超过 $2\cdot 10^7$。具体的分析是，修改次数等于 $\sum_{x=1}^{n-1}[\mu(x)\ne 0]\frac{n}{\mathrm{maxp}(x)}$，其中 $\mathrm{maxp}(x)$ 是 $x$ 的最大素因子。
时间复杂度 $O(F(n)+n\sqrt n)$。
D. Bracket Sequence
考虑 DP 计算一个给定字符串 $s$ 的方案数。$f(i,j)$ 表示 $S[0:i]$ 中等于 $\mathbb{()}^\infty[0:j]$ 的子序列的方案数，则答案就是 $f(|s|,2k)$。
令 $K=\max \{k\}$。对于第 $1$ 类区间询问，我们可以把这个 DP 写成 $v\cdot M_lM_{l+1}\cdots M_r$，其中 $M_i$ 是 $s_i$ 的转移矩阵。由于矩阵的特殊性质，可以在 $O(K^2)$ 的时间内计算一个矩阵乘上 $M_i$，因此只需要预处理 $M_1M_2\cdots M_i$ 和 $(M_1M_2\cdots M_i)^{-1}$，就可以在 $O(K)$ 时间内回答一个询问。
对于第 $2$ 类区间询问，首先可以添加一个 DP 状态，表示还没有进入子串，同时预处理 $M_1M_2\cdots M_i$ 的前缀和即可。
总时间复杂度 $O(nK^2+qK)$。
E. Dominating Point
令 $S(u)=\{v\mid (u,v)\in E\lor u=v\}$。点 $u$ 是支配点当且仅当不存在 $v\ne u$ 满足 $S(u)\subset S(v)$。
把所有点按度数从大到小排序，依次检查是否存在这样的 $v$。显然我们只需要检查已经确定是支配点的 $v$，而找到三个支配点后就可以直接返回，因此对于每个 $u$ 只需检查 $O(1)$ 个点，每次检查 $O(n)$。
总时间复杂度 $O(n^2)$。
F. An Easy Counting Problem
因为 $p$ 是素数，由 Lucas 定理可知组合数是 $p$ 进制下每一位组合数的乘积。$0\le b\le a< p$ 的组合数分布可以 $O(p^2)$ 暴力计算。
求出一位的组合数分布后，我们要计算其在 $i,j\to i\cdot j\bmod p$ 卷积意义下的 $k$ 次幂。通过找一个原根并将下标取离散对数的变换，我们可以将其转化为普通的循环卷积，可以用 FFT 优化。
时间复杂度 $O(p^2+p\log p\log k)$。
G. An Easy Math Problem
我们加上 $\gcd(p,q)=1$ 的限制，不同的 $(p,q)$ 就对应了不同的 $r$。考虑计算这样的 $(p,q)$ 的方案数。显然方案数是积性的，即每个素数独立，且 $p^k$ 的方案数是 $2k+1$（$(1,1),(p^i,1),(1,p^i)$）。分解 $n$ 之后直接计算即可。
可以预处理素数来加速分解，时间复杂度 $O(\sqrt N+q\frac{\sqrt N}{\log N})$。
H. Elimination Series Once More
我们对每个 $i$，和每个 $j=1,2,\ldots,n$，来计算 $i$ 能不能赢下第 $j$ 轮，也就是能不能让 $a_i$ 变成其所在的大小为 $2^j$ 的子树的最大值。
只需要判断两个条件：
- 所在子树中大于 $a_i$ 的不超过 $k$ 个。每次最多只能把一个换出去。
- $a_i\ge 2^j$。这是为了保证有足够多小的数放进子树。
这个条件可以在归并排序的过程中快速判断，时间复杂度 $O(n2^n)$。
I. Max GCD
我们枚举 $\gcd=d$，看是否能用 $d$ 的倍数满足条件。显然对于固定的 $j$，$i$ 应该越大越好，$k$ 在满足 $k-j\ge j-i$ 的前提下越小越好。
考虑从大到小枚举 $j$，找到对应的 $i$ 和 $k$。$i$ 可以直接找到，但 $k$ 并不单调。然而如果 $i$ 更小的时候 $k$ 更大，这样的三元组一定是不优的，因此仍然是只需要让 $k$ 单调下降。令 $A=\max\{a_i\}$，$d(A)$ 是 $1$ 到 $A$ 中约数个数的最大值，则可以在 $O(nd(A))$ 的时间中找到所有的三元组。
询问就是简单的二维偏序，为了平衡复杂度，可以使用 $O(1)$ 修改、$O(\sqrt n)$ 查询的分块，总时间复杂度 $O(nd(A)+q\sqrt n)$。
J. Graph Changing
考虑在 $G_1$ 中，两点有边当且仅当 $|u,v|\ge k$，如果 $u,v$ 可达，则最短路径长度一定不超过 $3$（$u\to 1\to n\to v$）。因此如果 $k>3$，$G_2$ 开始就是空图。
当 $k=3$ 时，显然当 $n$ 足够大时 $G_2$ 开始也是空图。
当 $k=2$ 时，显然当 $n$ 足够大时 $G_{i+1}$ 是 $G_i$ 的反图。
当 $k=1$ 时，显然 $G_1$ 开始就是完全图。
因此只需要预处理 $n$ 小的情况（例如 $n< 10$），特判 $k=1,2,3$，剩余的情况分类讨论答案是 $1,2,3$ 即可。
K. Penguins in Refrigerator
先求方案数，考虑从大到小插入数。首先大于 $M/2$ 的数相对顺序不改变，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，则 $a_i$ 只能插入到这个区间中。注意到这些区间形成一棵树形结构，因此方案数就是每个数插入的方案数相乘。
再求字典序最小的方案数。大于 $M/2$ 的数相对顺序不改变，可以连一条链。对于不超过，对于不超过 $M/2$ 的每个数 $a_i$，找到左右第一个大于 $M-a_i$ 的数，只需要它们之间的相对顺序不改变即可（因为其他的顺序关系都通过链确定了）。之后用堆维护，求字典序最小的拓扑排序即可。
时间复杂度 $O(n\log n)$。
L. Prism Palace
所求的就是随机旋转一个角度，有一条边在 $y$ 轴上的投影是整个凸包的概率。对于相邻的两个内角 $a,b$，这条边满足条件的角度范围是 $\max\{0,\pi-a-b\}$。对这些角度求和然后除以 $2\pi$ 即可。时间复杂度 $O(n)$。
M. Random Variables
考虑对每个 $k$ 计算每种数出现次数不超过 $k$ 的方案数。其等于 $$ n![x^n]\left(\sum_{i=0}^k\frac{x^i}{i!}\right)^m $$ 注意由于模数不一定是素数，所以不一定有阶乘逆元，但 EGF 的卷积只需要乘上组合数。
考虑容斥，即把 $\sum_{i=0}^k\frac{x^i}{i!}$ 写成 $e^x-\sum_{i=k+1}^\infty \frac{x^i}{i!}$。如果能够预处理所有 $\left(\sum_{i=k}^\infty \frac{x^i}{i!}\right)^m$，就能够在 $O(n^2\log n)$ 时间内计算答案（因为 $mk\le n$）。
这里 $m$ 的范围是 $\frac{n}{k}$，按照 $k$ 从大到小预处理，每次只需给内部的式子加上一项，展开后是 $O(m)$ 项已知的式子求和。因此可以在 $O\left(\sum_{k=1}^n \frac{n^3}{k^2}\right)=O(n^3)$ 时间内预处理所有的值。对于每组数据，还要对 $0\le i\le n$ 计算 $m\choose i$，可以通过快速幂计算 $(1+x)^m\bmod x^{n+1}$ 在 $O(n^2\log m)$ 的时间内计算。因此总复杂度是 $O(N^3+\sum n^2(\log n+\log m))$。
对于整数 $B$，我们只预处理 $k\ge B$ 的值，复杂度是 $O\left(\frac{n^3}{B}\right)$。对于 $k< B$，我们要计算的是一个短多项式的幂，可以通过 ODE（$f'g=mg'f$）来计算，注意 EGF 的求导就是移位，所以不需要除法，复杂度是 $O(nk)$。总时间复杂度 $O\left(\frac{N^3}{B}+\sum n B^2+\sum n^2(\log n+\log m)\right)$。
官方题解里有 $O(\sum n^2\log n)$ 的做法。
N. Python Program
外层循环直接模拟，内层循环用等差数列求和。
时间复杂度 $O(|a-b|)$。