A. Counting Permutations
对于所有满足条件的排列，二元组序列 $(a_{p_i}\bmod m_1,a_{p_i}\bmod m_2)$ 一定是相同的，也就是按 $a_i\bmod m_1$ 为第一关键字，$a_i\bmod m_2$ 为第二关键字升序排序。
如果这个序列不合法则无解，否则方案数为每个 $(a_i\bmod m_1,a_i\bmod m_2)$ 二元组出现次数的阶乘乘积。
时间复杂度 $O(n\log n)$。
B. Bookshelf Tracking
如果只有 E 操作，则维护每本书的位置，就可以 $O(1)$ 进行交换。
如果有 R 操作，注意到 R 操作的本质是将位于前一半的书按编号降序排序，后一半的书按编号升序排序。因此，在最后一次 R 操作之前，只需维护每本书是在前一半还是后一半。排序后再处理最后的一段 E 操作即可。
时间复杂度 $O(n+q)$。
C. Painting Fences
最优解一定是从一个极大全黑矩形开始扩展。这样的矩形共有 $O(nm)$ 个，可以通过枚举底端然后笛卡尔树求出。
考虑求从一个矩形扩展到全部的步数。显然两维是独立的，因此只需要考虑 $[l,r]$ 扩展到 $[0,n]$ 的最少步数。
如果 $l=0$ 或者 $r=n$，显然最优解是长度每次翻倍。
对于一般情况，枚举 $l=0$ 和 $r=n$ 哪个先满足。不妨设 $l=0$ 先满足。设初始时 $d=\left\lceil \frac{l}{r-l}\right\rceil$，则至少需要 $\left\lceil\log_2{(d+1)}\right\rceil$ 步。但是一直向左对称可能会导致一些浪费。事实上，最优解是：第 $i$ 轮，如果 $d$ 的二进制从低到高第 $i$ 位是 $1$，则向左对称，否则向右对称。
因此从一个矩形开始扩展的最小步数可以在 $O(\log nm)$ 甚至 $O(1)$ 的时间内求出。
总时间复杂度 $O(nm\log nm)$ 或 $O(nm)$。
D. Function with Many Maximums
首先要注意到，假设 $a_i$ 是降序排序，则 $f(a_i)=\sum_{j=1}^ia_j+ia_i$。如果不考虑 $a_i$ 必须是整数的条件，令 $a_i=\frac{1}{i(i+1)}$ 可以使所有 $f(a_i)$ 相同。
考虑找一个大数 $M$（大约为 $Cn^4$ 级别），然后令 $a_i=\left\lfloor \frac{M}{i(i+1)}\right\rfloor$，然后对其进行调整。我们希望使得 $f(a_{n}),f(a_{n-2}),f(a_{n-4}),\ldots,f(a_{n-2(b-1)})$ 是最大值，因此对于 $i< n-2(b-1)$，只需令 $a_i=a_{i+1}+1$。注意这时 $a_1$ 也就是 $a_i$ 的最大值不超过 $O(Cn^2)$，符合题目要求。
对于后面部分的调整，首先需要将 $f(a_i)$ 调整成递增，这只需将函数值下降位置的 $a_i$ 增加 $O(n)$ 的值。这是因为原来相邻函数值的差是 $O(n)$ 的，所以调整后累计的差是 $O(n^2)$，而将 $a_i$ 增加 $1$ 会使得 $f(a_i)$ 增加 $i+1$。
调整后，相邻函数值的差仍然是 $O(n)$ 的，而相邻 $a_i$ 的差是 $\Theta(Cn)$，因此将 $a_{2i+1}$ 的值减少 $f(a_{2i+2})-f(a_{2i})$ 就能使得 $f(a_{2i+2})=f(a_{2i})$。
E. Building a Fence
分类讨论。不妨设 $w\le h$。
- 如果 $s\le w\le h$，那么从一个角开始贪心铺放，不可能出现一个 $s$ 被分成三段的情况，因此答案可以取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
- 如果 $w\le h< s$，那么答案可能是 $2,3$ 或 $4$。
- 要答案为 $2$，只可能是两个 $s$ 都被分成了两段，即 $w+h=s$。
- 要答案为 $3$，肯定有 $k$ 个 $s$ 恰好拼了 $k+1$ 条边。
- $k=1$，即 $2w=s$ 或 $2h=s$。
- $k=2$，即 $2w+h=2s$ 或 $2h+w=s$。
- $k=3$，即 $2(w+h)=3s$。
- 否则答案为 $4$。
- 如果 $w< s\le h$。
- 如果 $2w+h\ge 2s$，那么可以先拿两个 $s$ 分出两个 $w$，剩下部分拼到同一个长边，然后从这条边开始贪心，能取到下界 $\left\lceil \frac{2(w+h)}{s}\right\rceil$。
- 否则答案为 $3$ 或 $4$，分析同上，但因为大小关系的限制只可能 $k=3$，即 $2(w+h)=3s$。
F. Teleports
注意到经过任意的操作后，我们都知道可能的宝藏位置是一个区间。设 $f(l,r)$ 是已知宝藏在第 $l$ 个到第 $r$ 个箱子时，找到宝藏的最小代价。
转移如下。
- 枚举选择的传送器 $x$，则新的可能的宝藏范围是 $[2x-r,2x-l]$。
- 如果 $1\le 2x-r\le 2x-l\le n$，则 $f(l,r)\le f(2x-r,2x-l)$。
- 如果 $2x-r< 1$，则 $[2x,r]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(1,2x-l),f(2x,r)\}$。
- 如果 $2x-l>n$，则 $[l,2x-n-1]$ 中的宝藏无法传送，$f(l,r)\le \max\{f(2x-r,n),f(l,2x-n-1)\}$。
注意到转移图是一个关于区间长度 $r-l$ 的分层图，每一层中只有第一类转移。因此可以从小到大枚举 $r-l$，执行所有的第二、三类转移，然后使用 Dijkstra 进行第一类转移。这里是稠密图所以可以使用 $O(n^2)$ 的 Dijkstra（当然堆优化的 Dijkstra 也很快）。
时间复杂度 $O(n^3)$。
G. Exponent Calculator
因为只有加法、减法和乘法，因此不考虑牛顿迭代。考虑用 $e^x=\sum_{n=0}^\infty \frac{x^n}{n!}$ 来逼近。但是这样在 $|x|$ 较大时收敛较慢。因此考虑先将 $x$ 除以 $2^B$，然后展开到 $x^T$ 项，最后将结果平方 $B$ 次。实验可以发现 $T=7,B=10$ 时较优，可以在 $x=20$ 时达到 $10^{-12}$ 以下的相对精度。
H. Ancient Country
考虑所有城市的顶点，不可能出现 $i < j < k < l$ 满足 $P_i$ 和 $P_k$ 在同一个城市，并且 $P_j$ 和 $P_l$ 在同一个城市（否则 $P_iP_k$ 和 $P_jP_l$ 就会相交或是在国家范围之外）。因此这些城市的顶点形成一个树形结构。即设包含最小顶点的城市的顶点为 $P_{i_1},P_{i_2},\ldots,P_{i_k}$，那么剩余的城市顶点一定分布在 $[i_1+1,i_2-1],[i_2+1,i_3-1],\ldots,[i_k+1,n]$ 这些区间中。
因此我们可以设计区间 DP，即 $f(l,r)$ 表示只是用下标在 $l$ 到 $r$ 的顶点，所构造城市的最大保护级别。转移如下。
假设 $P_l$ 不属于某个城市，则 $f(l,r)\gets f(l+1,r)$。
否则我们要选一个包含 $P_l$ 的凸包，然后用凸包的权值加上凸包顶点间的区间的 $f$ 值之和来更新 $f(l,r)$。这一步也可以用 DP 进行。
- 首先枚举 $i$ 连的第一条边 $P_iP_s$，然后令 $g(j,k)$ 表示凸包最后一条边是 $P_jP_k$ 的最大权值。转移是枚举下一条边 $P_kP_e$，然后转移到 $g(k,e)$。最后检查一下连回 $l$ 是否合法并更新答案。需要枚举第一条边是因为要检查 $P_kP_iP_s$ 这个角是否合法。注意这里判断凸包只需要相邻三个点的夹角，因为下标递增，必然是不会自交的。
具体实现时，可以从大到小枚举 $l$，然后进行 DP。枚举 $l,s$ 后，DP 的复杂度是 $O(n^3)$。注意到转移可以用极角序优化，即枚举 $k,e$，可以转移到 $g(k,e)$ 的 $i$ 是极角序上的一段。事实上，我们不需要记录极角序，因为下标递增，每个点所连出的边按下标排序就是极角序，因此枚举 $k,e$ 后，可以转移的 $i$ 是一个前缀，用双指针维护即可。
总时间复杂度 $O(n^4)$。
I. Marks Sum
如果长度小于 $2\,000$，可以直接返回 $d=info=0$。
如果长度大于等于 $2\,000$，我们一定能找到一个前缀，使得剩余字符数小于 $2\,000$，且总和是 $2\,000$ 的倍数或其加 $1$。我们令 $info=2x+y$（$0\le y\le 1$）表示前缀的总和等于 $2\,000x+y$。因为字符串长度不超过 $10^6$，因此 $x< 1\,000$，是足够的。
第二次时只需根据 $info$ 计算出前缀的总和，在加上输入串的总和即可。
J. Prefix Divisible by Suffix
枚举选择最短的后缀。如果后缀有前导 $0$，则去掉之后仍然满足条件。因此满足条件的最短后缀长度不超过 $7$（如果大于 $7$ 则前缀小于后缀）。
因为我们钦定枚举的后缀是最短的一个，需要枚举更短的一些进行容斥。若干后缀都满足的数形如 $km+a$，可以用扩展欧几里得算法求出。
时间复杂度 $O(10^7\cdot 2^7\cdot \log n)$。但是注意到在后缀较长时，对于很多的集合，满足条件的数的大小都超过了 $n$。我们在枚举的时候对这种情况直接剪枝，总枚举次数实际上远小于这个上界。
K. Train Depot
首先可以把所有列车转化为 $s_i$ 到 $t_i$ 的路径（$t_i$ 是 $s_i$ 的祖先），价值为 $c_i$，然后选择若干条点不相交的路径使得总价值最大。
设 $f(x)$ 为在 $x$ 的子树里面选择路径的最大价值。如果 $x$ 不是某条路径的顶端则 $f(x)\gets \sum_{y\in ch(x)}f(y)$。
如果选择了 $x\to y$ 的路径，那么 $y$ 到 $x$（不包括 $x$）的路径上的每一个点的兄弟以及 $y$ 的所有孩子 $z$ 会贡献 $f(z)$。反过来考虑，每个点 $x$ 会对底端是 $x$ 的父亲或 $x$ 的兄弟子树中的点的路径有贡献，在 DFS 序上即 $[in_{parent_x},in_x)$ 和 $[out_x,out_{parent_x})$ 这两个区间。使用线段树或树状数组维护这个贡献即可。
时间复杂度 $O((n+\sum k_i)\log n)$。
L. Array Spread
二分答案 $x$，如果有一种序列满足每个区间的总和在 $[1,x]$ 中，说明答案不大于 $x$。
设 $s_i$ 是前 $i$ 个数的和，则限制为 $s_i\ge s_{i-1}$ 和 $1\le s_{r_i}-s_{l_i-1}\le x$，显然是差分约束的形式。离散化之后点数和边数都是 $O(m)$，因此判断负环的时间复杂度是 $O(m^2)$。这里也可以看出答案是分子和分母不超过 $O(m)$（分母不超过简单环长度也就是图中点数，分子不超过图中除 $x$ 外的边权和）的分数。因此二分次数是 $O(\log m)$，二分之后可以根据实数值还原答案。也可以直接对这 $O(m^2)$ 个分数二分。
总时间复杂度 $O(m^2\log m)$。
事实上，我们可以去掉二分。将边权为 $x$ 的边称为特殊边，剩下的是普通边。令 $f(i,v)$ 表示从任意点开始，经过恰好 $i$ 条特殊边，到达 $v$ 的路径的普通边边权和的最小值。则答案等于 $$ \max_v\min_{i=0}^{n-1}\frac{f(i,v)-f(n,v)}{n-i} $$
其中 $n$ 是顶点数。
证明见此论文。
M. Uniting Amoebas
每次将最大值和相邻的合并就可以做到 $\sum_{i=1}^n a_i-\max_{i=1}^n\{a_i\}$。
显然这是最优解，因为每次花费 $v$ 的代价至多使得最大值增加 $v$。