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|)$。

A. Bus Analysis

不妨将价格除以 $2$，变为 $1$ 和 $3$，最后将答案乘 $2$ 即可。

先考虑对于给定的 $t_1,t_2,\ldots,t_n$，如何计算最小代价。

设 $\mathrm{dp}(i,j)$ 表示用 $j$ 的代价覆盖了前 $i$ 个点，最多还能覆盖多长的距离。设覆盖前 $i$ 个点的最小代价为 $x$，则只有 $f(i,x),f(i,x+1),f(i,x+2)$ 的值有用。这是因为在如果前 $i$ 个点花费了至少 $x+3$ 的代价，一定不比“花费 $x$ 的代价覆盖前 $i$ 个点，然后再买一张 $3$ 元的票”优。

于是，在 DP 的过程中我们只需要记录 $x,f(i,x),f(i,x+1),f(i,x+2)$ 这些值。现在变为计数问题，只需要将这些值记在状态里面。并且注意到，我们只需要求代价的和，所以不需要将 $x$ 计入状态，只需在代价变大时统计进答案。

时间复杂度 $O(n\cdot 75^3)$。实际上，状态数的常数非常小，有用的三元组 $(a,b,c)$ 都满足 $0\le a\le a+20\le b\le b+20\le c\le 75$。

B. Missing Boundaries

首先，对于已经确定两个端点的区间，它们一定不能相交。

对于已经确定一个端点的区间，确定的端点一定不能包含在已经确定的区间里面，且互不相同。

剩下的区间可以任意填，我们可以计算出最小和最大的可能区间数量，判断输入的区间数量是否在范围内即可。

最大的区间数量就是（$L-$ 两端点确定的区间的长度和 $-$ 一个端点确定的区间个数）。

最小的区间数量就是相邻且差大于 $1$ 的右端点和左端点的对数（包括开头和结尾）。

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

C. Price Combo

考虑最终方案中每个物品是在商店 A 购买还是商店 B 购买。注意到如果 $a_i>a_j$ 且 $b_i< b_j$，那么在商店 A 购买物品 $i$ 、商店 B 购买物品 $j$ 一定是不优的（交换之后一定不劣）。因此，假设我们把一个物品看做点 $(a_i,b_i)$，那么一定存在一条右上到左下的折线，折线上以及左上方的物品在商店 A 购买，折线右下方的物品在商店 B 购买。我们对这条折线进行 DP。

不妨设 $a_i,b_i$ 互不相同。我们考虑从右上到左下确定折线，当折线向左的时候，加入折线上方的 $a_i$ 产生的贡献；折线向下的时候，加入折线右方的 $b_i$ 产生的贡献。注意因为是买一送一，因此只有第 $1,3,5,\ldots$ 个会产生贡献。

显然我们只需要将 $(a_i,b_i)$ 作为折线的关键点。为了方便起见，我们可以加入 $(+\infty,+\infty),(-\infty,-\infty)$。

设 $\mathrm{dp}(i,p,q)$ 是折线走到了 $(a_i,b_i)$，选择的 $a$ 个数奇偶性是 $p$，$b$ 个数奇偶性是 $q$ 的最小代价。那么假设 $(a_i,b_i)$ 从 $(a_j,b_j)$ 转移来（$a_i< a_j,b_i< b_j$），则需要加上的贡献是 $a_i< a_k< a_j$（$b_k>b_j$）和 $b_i< b_k< b_j$（$a_k>a_i$），以及 $a_i$ 的贡献。

考虑按照 $a_i$ 从大到小扫描线，用线段树维护转移。线段树以 $b$ 作为下标，维护 DP 值加上 $a_k$ 的贡献的最小值。对于 $a_k$ 的贡献，只需在扫描线时在线段树上做前缀加（$b_j< b_k$）。注意这里的加法标记实际上是（$0$ 位置加上的值，$1$ 位置加上的值，加的数的个数）三元组。对于 $b_k$ 的贡献，考虑直接在线段树上维护，即每个结点维护 $\mathrm{dp}(j)$ 加上小于 $b_j$ 的 $b$ 的贡献后的最小值，以及 $b$ 的贡献。这里 $b$ 的贡献本质上和 $a_k$ 的加法标记一样。合并时，DP 值应当是左区间的 DP 值以及（右区间的 DP 值加上左区间 $b$ 的贡献）的较小值。这样，要求 $\mathrm{dp}(i)$，只需要在线段树上查询后缀 $(b_i,+\infty)$。

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

D. Data Determination

不妨设 $a_1\le a_2\le \cdots\le a_n$。

当 $k$ 是奇数时，需要存在 $i$，满足 $a_i=m,i-1\ge\frac{k-1}{2},n-i\ge\frac{k-1}{2}$。

当 $k$ 是偶数时，需要存在 $i< j$，满足 $a_i+a_j=2m,i-1\ge \frac{k}{2} -1,n-j\ge\frac{k}{2}-1$。注意对于相同的 $(a_i,a_j)$，$i$ 和 $j$ 离得越近越好，这样的 $(i,j)$ 只有 $O(n)$ 对。

时间复杂度 $O(n\log n)$。

E. Express Eviction

解法 1

最小割。注意到存在路径当且仅当不存在左下区域到右上区域、每个格子都有居民、且相邻格子行列差都不超过 $2$ 的路径。我们认为左下边界和左下区域是相邻的，右上边界和右上区域是相邻的。

因此我们可以对每个有居民的格子建两个点 $(a_u,b_u)$，如果它是左下边界则连边 $(S,a_u,+\infty)$，右上边界则连边 $(b_u,T,+\infty)$，同时连边 $(a_u,b_u,1)$ 代表可以花费 $1$ 的代价删除这个格子。对于行列差都不超过 $2$ 的每对格子 $u,v$，连边 $(b_u,a_v,+\infty)$。这个图的最小割即为答案。

时间复杂度 $O(\mathrm{Maxflow}(HW,HW))$。

解法 2

最短路。考虑普通的最短路在什么时候会得不到最优解。

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

如这个例子，只需删除第三行的第四个格子。我们注意到这样的路径实际上是经过了一个格子相对的两个角，但我们的状态中并没有记录经过的格子，所以导致重复计算代价。

考虑所有经过两次的格子，如果一个有居民的格子 $u$ 的两次经过在另一个格子 $v$ 的两次经过之间，我们不如额外花费 $1$ 的代价直接穿过格子 $v$。因此可以假设没有这样的两个格子 $(u,v)$。在这个前提下，我们可以发现路径上的每一个点至多在两个格子的两次经过之间（路径的两侧各一个），通过在状态中记录这两个格子，我们可以做到 $O(H^3W^3)$ 的时间复杂度。

进一步地，假设我们依次经过了格子 $u,v$，那么下一步一定是从 $v$ 走到格子 $u$ 的对角。并且如果在下一次经过 $u$ 之前我们花费了额外的代价，也是不如直接穿过 $u$ 的。因此我们只需要记录一个之前经过的格子，并加一种额外的转移，即当前位置是 $x$，经过了 $v$，对于 $v$ 的每个对角相邻的点 $w$，如果 $x$ 可以不花费额外代价到达 $w$，则可以直接转移到位置 $w$，经过了 $x$。转移可以通过从每个点 BFS 预处理。

时间复杂度 $O(H^2W^2)$。

F. Fibonacci Fusion

不妨设 $a_1\le a_2\le \cdots\le a_n$。

枚举 $j$，则 $a_j< a_i+a_j\le 2a_j$，满足这样条件的斐波那契数只有至多两个，假设我们能求出这两个斐波那契数，就只需要求某个数的出现次数。

由于 $a_i$ 非常大，对应的斐波那契数也非常大，所以我们计算斐波那契数对大素数取模的值（避免碰撞），同时需要估算对应的数的下标。

因为 $F_n=\frac{1}{\sqrt5}\left(\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right)\approx \frac{1}{\sqrt 5}\left(\frac{1+\sqrt5}{2}\right)^n$ ，所以可以用 $n\approx \log_{\frac{1+\sqrt 5}{2}}{\sqrt 5a_i}$ 来估算。

时间复杂度 $O(n\log n+\sum\log a_i)$。

G. Game of Geniuses

答案等于 $\max_i\min_j a_{ij}$。

设答案为 $x$，答案大于等于 $x$ 是平凡的，先手可以删除除最小值等于 $x$ 的行以外的其余行。

要证明答案小于等于 $x$，我们只需要证明每轮后，后手都能保证每行都有小于等于 $x$ 的数。不妨设先手删除了第一行，则后手找到剩余 $n-1$ 行中各一个小于等于 $x$ 的数，标记其所在列，然后删除未被标记的列即可。

时间复杂度 $O(n^2)$。

H. Henry the Plumber

因为每个水管都必须立即转弯，所以答案至少是 $2$。

而答案不超过 $4$，因为可以分别连平行于 $z$ 轴的水管，到同一个 $z$ 之后垂直于 $z$ 轴连接起来（如果两点连线平行于 $z$ 轴则直接连）。

分类讨论：

• 如果 $(x_1,y_1,z_1)-(x_2,y_2,z_2)$ 垂直于 $(p_1,q_1,0)$ 和 $(p_2,q_2,0)$，则答案为 $2$。
• 否则答案至少为 $3$。答案为 $3$ 当且仅当存在一个中间点 $P$，和 $(x_i,y_i,z_i)$ 的连线垂直于 $(p_i,q_i,0)$。即 $P$ 在经过 $(x_i,y_i,z_i)$ 且垂直于 $(p_i,q_i,0)$ 的平面上。
• 如果这两个平面平行，则答案为 $4$。
• 否则找到这两个平面的交，设为 $(x_0,y_0,z)$（一条平行于 $z$ 轴的直线）。现在要确定 $z$ 的值，使得 $P$ 的夹角为直角，即 $(x_0-x_1,y_0-y_1,z-z_1)$ 和 $(x_0-x_2,y_0-y_2,z-z_2)$ 的点积为 $0$。
• 如果 $(x_0,y_0)$ 和某个 $(x_i,y_i)$ 重合，则满足条件的 $P$ 就是 $(x_i,y_i,z_{j})$，如果 $z_1\ne z_2$ 则答案为 $3$，否则答案为 $4$（因为水管长度不能为 $0$）。
• 否则，条件是一个关于 $z$ 的二次方程，只需判断判别式是否大于等于 $0$。大于等于 $0$ 则答案为 $3$，否则答案为 $4$。

时间复杂度 $O(1)$。

I. ICPC Inference

枚举获得金银铜牌的队伍。铜牌一定是通过了一个题目，且罚时尽量大。金牌一定是通过了尽量多的题目，且罚时尽可能小。

我们可以将分数设为 $M\cdot \mathrm{num}-\mathrm{penalty}$，其中 $M$ 是一个非常大的数。则分数越大的人排名越高。

考虑银牌可能的分数，因为铜牌只通过一个题，银牌分数应当在不小于铜牌的前提下尽可能小，因此有用的分数只有通过一个题的情况以及通过两个题且罚时最大。设这些可能的分数是 $s_1< s_2< \ldots< s_k$，则满足 $s_i<\mathrm{bronze}\le\mathrm{gold}< s_{i+1}$ 的金铜牌是不合法的（当然还有小于 $s_1$ 和大于 $s_k$ 的情况）。

我们可以在 $O(\log N)$ 的时间里面对每一个区间计算答案，但是区间的数量可以是 $O(N^2)$ 的。注意到罚时 $K=20$ 比较小，而可能的罚时都形如 $t_i+K\cdot c$（$0\le c< i$），因此可能的罚时可以写成 $O(N)$ 个段，每个段以 $K$ 为周期。对于跨段的区间我们可以 $O(\log N)$ 计算。而对于段内我们可以抽象成 $O(K)$ 个以下询问：

• 有多少对 $(\mathrm{bronze},\mathrm{gold})$ 满足 $\mathrm{bronze}\bmod K=i$，$l\le \mathrm{bronze}\le r$ 且 $\mathrm{gold}-\mathrm{bronze}\le j$。

这样的 $(\mathrm{bronze},\mathrm{gold})$ 也只有 $O(NK)$ 对，预处理之后可以 $O(\log N)$ 回答询问。

注意金银铜牌必须互不相同，因此需要做一些容斥。

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

J. Juliet Unifies Ones

数据范围很小，所以做法很多。

一个线性的做法是分成三段，分别是 $0,1,0$，设 $\mathrm{dp}(i,j)$ 表示考虑 $i$ 个字符，目前在第 $j$ 段，至少要删几个字符。

K. Routing K-Codes

如果 $K(b)=\left\lfloor\frac{K(a)}{2}\right\rfloor$ 则我们将边定向为 $a\to b$。因为所有 $K(x)$ 互不相同，因此每个点的出度都不超过 $1$，入度不超过 $2$，且图中不存在环，因此只可能是内向二叉树。因此如果 $m\ne n-1$ 则无解。

假设确定了根，则根的值为 $0$ 或 $1$（度数小于 $2$ 则为 $0$，等于 $2$ 则为 $1$），深度不超过 $32$ 或 $31$，每个孩子的值是 $2K(x)$ 或 $2K(x)+1$。最小的代价和可以通过 DP 求出。使用换根 DP 即可求出每个点作为根的答案。

时间复杂度 $O(n+m)$。

L. Random Numbers

注意到长度为 $k$ 的区间的和的期望是 $k\cdot \frac{n+1}{2}$，因此当 $k$ 距离 $\frac{n}{2}$ 较近时才有较大的概率存在合法区间。当 $k$ 较小的时候，因为总的组合数量不多，因此也有一定的概率存在合法区间。

因此只需设置常数 $B$，枚举所有长度在 $[1,B]$ 或 $\left[\frac{n}{2}-B,\frac{n}{2}+B\right]$ 中的区间检查即可。

时间复杂度 $O(nB)$。例如 $B$ 取 $500$ 可以通过此题。

M. Mathematics Championships

答案等于前 $2^i$（$0\le i\le k$）大数和的最大值。排序后即可计算。

时间复杂度 $O(n2^n)$。

A. Coprime Array

注意到我们只关心 $s\bmod x$ 的值（答案绝对值要求在 $10^9$ 以内，但是任何一组解都可以通过调整符合这个范围，所以可以忽略这个限制），将 $x$ 分解后，只需要求出每个 $p^k$ 的解，就能通过 CRT 合并出 $x$ 的解。

显然答案等于 $1$ 当且仅当 $\gcd(s,x)=1$。

剩下的情况，除了 $s$ 是奇数且 $x$ 是偶数的情况，都能构造出长度为 $2$ 的解。

$s$ 是奇数且 $x$ 是偶数的情况可以先分出一个 $1$，因此可以构造出长度为 $3$ 的解。

实现时其实可以利用随机避免分解和 CRT，随机到一个解的概率至少是 $\prod_{p|x}\frac{\max\{1,p-2\}}{p}$。

B. Square Locator

因为点 $A$ 在 $y$ 轴上，所以点 $A$ 的坐标可以直接算出。枚举 $ABCD$ 是逆时针还是顺时针，设点 $B$ 的坐标是 $(x,y)$，则可以通过点 $B$ 和点 $C$ 到原点的距离列出两个方程，从而直接解出 $x,y$ 并判断。

C. -is-this-bitset-

对于深度 $d\le 11$ 的点 $i$，将 $a_i$ 设为 $2^{20-d}$。因为树是二叉树，所以至多改变 $2^{12}-1=4\,095$ 个点的 $a_i$。

改变之后，每条链上的前 $12$ 个点就可以凑出 $[0,2^{21})$ 中所有 $2^9=512$ 的倍数。因此对于 $d>11$ 的点，只需要考虑模 $512$ 的每种余数能凑出的最小的数，可以在 $O(512)$ 的时间 DP 求出。

为了进一步减小空间消耗，注意到每条链上 DP 的改变量不会超过 $\max\{b_i\} < 2^{21}$，因此只需记录 DP 数组发生的改变，回溯时撤销即可。

设 $V=\max\{b_i\},k=5\,000$，则时间复杂度为 $O(nV/k)$，空间复杂度为 $O(n+V)$。

D. Cycle Game

我们认为最外圈边界都是白格子，则存在一个内部非空的环当且仅当存在一个格子，将这个格子视为白格子后白格子的八连通块至少有两个（即存在一个白格子和边界不连通）。

加入一个黑格子后，如果存在这样的格子，那么其中的一个一定与新加入的格子相邻。因此只需使用线段树分治和可撤销并查集维护连通性，在每个时刻枚举周围的所有格子并判断这次操作是否应该进行。

时间复杂度 $O(nm\log ^2 (nm))$。

E. Sum of Squares

F. Alternating Cycle

G. Touching Grass

如果询问的是直线，则问题可以转化为直线和点集的上凸包是否相交，只需在凸包上二分。

线段询问可以通过线段树转化为直线询问，即按 $x$ 排序建线段树，对线段树上的每个区间都求凸包。

这样的空间复杂度是 $O(n\log n+m)$，采用类似分治的方式离线回答询问可以优化为 $O(n+m)$。

将线段按斜率排序后可以避免二分，改用双指针，总时间复杂度 $O((n+m)\log n)$。

H. Game Design

将 $i$ 到 $p_i$ 连边，可以看作每个点入度和出度都是 $1$ 的有向图。设 $f(i,j)$ 为考虑前 $i$ 个点，有 $j$ 条入边和出边的另一端还未确定（大于 $i$）。

考虑 $i$ 的连边，有如下四种转移。

• 入边和出边都向后，转移到 $j+1$，方案数 $1$。
• 入边向后，出边向前，转移到 $j$，方案数 $j$。
• 入边向前，出边向后，要求 $s_i=1$，转移到 $j$，方案数 $j$。
• 入边和出边都向前，要求 $s_i=1$，转移到 $j-1$，方案数 $j^2$。

时间复杂度 $O(n^2)$。

I. Geometry Hacking

J. Non-Interactive Nim

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$。

A. Arrested Development

动态规划，$f(i,j)$ 表示考虑前 $i$ 个任务，第一个人总时间为 $j$ 时，第二个人总时间的最小值。

时间复杂度 $O(n^2\max\{a_i,b_i\})$。

B. Champernowne Substring

讨论以下情况：

• 对于位置不超过 $100\,000$ 的情况暴力判断，以下都假设串中出现的都至少是五位数。

• 特判串中出现 $10^k$ 或 $10^k-1$ 的情况，以下都假设串中所有数的长度相等。

• 串中只包含一个数。问号一定贪心填 $0$（首位是 $1$），如果首位是 $0$ 还需要在前面补 $1$。

• 串中包含超过一个数。枚举这个数的开始位置和长度，以及进位的位数（因为串长不超过 $25$ 且都至少是五位数，因此至多有一次进位）。那么进位的部分全部填 $0$ 或 $9$，前一位枚举 $0$ 至 $9$，再之前的位每个数都一样，问号同样贪心填 $0$ 或 $1$。对于每种可能性都检查一遍。

C. Comparator

首先注意到，表达式只有两个输入，我们可以直接枚举这两个输入后求表达式的值。从而，每条语句的效果都可以拆分为不超过 $4$ 条：如果 $x$ 的第 $a$ 位为 $u$ 且 $y$ 的第 $b$ 位为 $v$，则返回 $r$。当两条语句的 $(a,u,b,v)$ 四元组相同时，靠后的语句实际上没有任何效果，因为它所能作用的输入已经全部返回了。因此，我们实际上只需要考虑不超过 $4k^2$ 条语句，每条语句的效果可以在 $O(2^{2k})$ 的时间内暴力处理。

当我们得到了所有 $f(x,y)$ 的值后，就可以统计答案。前两个答案都可以暴力统计，最后的答案枚举 $x,y$ 后使用 bitset 优化即可。

时间复杂度 $O\left(\sum|expr|+k^22^{2k}+2^{3k}/w\right)$。

D. Dihedral Group

二面体群的操作对应到字符串其实就是翻转和循环移位，只需要判断未翻转/翻转的 $d+d$ 是否包含 $t$ 作为子串。

时间复杂度 $O(n)$。

E. House Deconstruction

1. $n=m$ 的情况

首先考虑 $n=m$ 的情况，即人的数量和房子的数量一样多时，如何求最小代价。对于一个方案，设 $c_i$ 表示经过了 $i$ 到 $i+1$ 这条边的人数（这里模 $x$ 相等的下标表示同一个位置，例如 $x+1$ 代表 $1$）。如果是从 $i+1$ 到 $i$ 则 $c_i$ 是经过人数的相反数，显然最优解中不会有一条边两个方向都有人经过。则方案对应的代价是 $\sum_{i=1}^x|c_i|$，需要满足的限制如下：

• 如果 $i$ 位置是人，则 $c_i=c_{i-1}+1$。
• 如果 $i$ 位置是房子，则 $c_i=c_{i-1}-1$。
• 如果 $i$ 位置是空，则 $c_i=c_{i-1}$。

容易发现，$c_i$ 序列几乎是确定的，除了可以整体加上一个任意整数。设一个合法的序列是 $c_i'$，则最小代价为对于任意 $k$，$\sum_{i=1}^x|c_i+k|$ 的最小值。这个函数关于 $k$ 是下凸的，因此可以用三分求出答案。（事实上，$k$ 一定是 $c_i$ 的中位数的相反数。）

2. $n< m$ 的情况：最优解

延续 $n=m$ 的思路，我们可以稍微修改 $c_i$ 的定义，即如果 $i$ 位置是房子，$c_i$ 可以等于 $c_{i-1}-1$ 或 $c_{i-1}$（表示该房子未被选择）。我们可以猜测以下的引理：

引理 1 设 $g(k)$ 为 $c_x=k$ 时的最优解，则 $g(k)$ 是下凸函数。

有了引理 1 之后，对于 $n< m$ 的情况我们同样可以三分 $k$，之后只需解决固定 $c_x$ 之后的问题，即可求出最优解。

引理 1 的证明 只需证明 $2g(k)\le g(k-1)+g(k+1)$。设 $k-1$ 和 $k+1$ 对应的序列分别为 $c_i^{(k-1)}$ 和 $c_{i}^{(k+1)}$。则令 $c_i^{(k)}=\frac{c_i^{(k-1)}+c_i^{(k+1)}}{2}$。该序列几乎满足我们的需求，包括 $c_x^{(k)}=k$ 以及相邻 $c_i$ 之间的关系，并且因为三角形不等式 $|a+b|\le |a|+|b|$，该序列的代价不超过 $\frac{g(k-1)+g(k+1)}{2}$。唯一有问题的地方是当某一处房子只在 $k-1$ 和 $k+1$ 中的一个方案中被选择时，我们会算出 $c_i=c_{i-1}-1/2$。然而，对于每一个极长的小数部分为 $1/2$ 的连续段，整体加上或减去 $1/2$ 就是合法的序列，且其中的一种不会使得代价变大（只需比较正数和负数的数量）。从而我们证明了 $2g(k)\le g(k-1)+g(k+1)$。$\blacksquare$

对于证明中存在小数部分的调整，事实上，即使我们把 $i$ 位置是房子时的限制改为 $c_i\in[c_{i-1}-1,c_i]$，最优解仍然会在所有数都是整数时取到。（提示：仍然可以考虑调整，也可以直接把原问题写成费用流，这样也能得到原问题的凸性。）

接下来只需要考虑固定 $k$ 时如何求最优解。我们可以使用 DP。

设 $f(i,j)$ 表示考虑了前 $i$ 个位置，$c_i=j$ 的最小代价。初始值为 $f(0,k)=0$。转移如下：

• 如果 $i$ 位置是人，则 $f(i,j)= f(i-1,j-1)+|j|$。
• 如果 $i$ 位置是房子，则 $f(i,j)= \min \{f(i-1,j+1),f(i-1,j)\}+|j|$。这里代表房子可选可不选。
• 如果 $i$ 位置是空，则 $f(i,j)=f(i-1,j)+|j|$。

最终的答案即为 $f(x,k)$。

注意到 $f(i,j)$ 对于固定的 $i$，关于 $j$ 是下凸的，很容易维护。实现中，为了方便，可以把状态改为 $f(i,j)$ 表示前 $i$ 个位置选了 $j$ 个房子的最小代价，这时最小值的位置一定是单调不降的，可以用差分维护最小值之后的斜率，对于房子只需插入一个 $0$ 的斜率。

把空的位置一起处理，就能做到 $O(m)$ 的时间复杂度。

因此，我们可以在 $O(m\log n)$ 的时间内求出最优解。

3. $n< m$ 的情况：方案数

为了计算方案数，我们还需要以下的引理：

引理 2 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。

证明 注意到对于一个全局最优解的匹配方案，每个未选择的房子 $i$ 都应该满足 $c_i=0$，即没有匹配经过该房子，否则用该房子替换这个匹配中的房子，代价严格变小。如果一个全局最优解 $S$ 在两个不同的 $k$ 处取到最优解，那么一定有一个 $k$ 使得某个未选择的房子 $i$ 满足 $c_i\ne 0$，矛盾。因此， 一个全局最优解 $S$ 只会在唯一的 $k$ 处取到最优解。$\blacksquare$

根据引理 2，我们只需对每个 $g(k)$ 取到最小值的 $k$ 分别计算方案数并求和即可。

我们还需要以下引理：

引理 3 至多有两个 $k$ 满足 $g(k)$ 是最小值。

证明 采用反证法，假设 $g(k-1),g(k),g(k+1)$ 都是最小值。根据引理 1 的证明过程，$g(k)=\frac{g(k-1)+g(k+1)}{2}$ 的必要条件是 $c_i^{(k-1)}\cdot c_i^{(k+1)}\ge 0$（否则三角形不等式严格不等），以及对于每个极长的小数部分为 $1/2$ 的连续段，正数的个数等于负数的个数（从而无论加还是减 $1/2$，都不会改变代价）。因此不妨设 $k-1\ge 0$（$k+1\le 0$ 是对称的），找到最小的 $j$ 满足 $c_j^{(k-1)}\ne c_j^{(k+1)}-2$，则 $j$ 位置是房子。这样的 $j$ 一定存在，否则两个方案对应相同的 $S$，根据引理 2，一定不是全局最优解。此时 $c_j^{(k-1)}=c_j^{(k+1)}-3$ 或 $c_j^{(k-1)}=c_j^{(k+1)}-1$，且 $c_j^{(k-1)}\ge 0$。无论如何，我们都可以令 $c_{j}^{(k)}=c_{j-1}^{(k)}>0$，同时调整极长的连续段。但是因为 $j$ 是未选择的房子，所以这一定不是全局最优解。因此至多有两个 $k$ 满足 $g(k)$ 是最小值。$\blacksquare$

根据引理 3，我们只需要对至多两个 $k$ 分别计算方案数并求和。因此这不会增加我们的复杂度。

至于计算方案数，可以在 DP 的过程中同时进行。我们维护 DP 取到最小值的位置，并且最小值至多有两个。最小值之后的部分的方案数只需进行一个平移。因为最小值的位置单调不降，方案数也很容易维护，时间复杂度仍然为 $O(m)$。

综上，我们可以在 $O(m\log n)$ 的时间复杂度内解决该问题。

F. Magic Bean

我们只需要构造出能够交换两个环内的豆子的操作，之后每次找到 $a$ 环内的 $b$ 豆子，和 $b$ 环内非 $b$ 的豆子交换，即可在不超过 $30$ 次交换内完成复原。

构造的操作如下：把 $a$ 环内要交换的豆子移至 $1$，$b$ 环内要交换的豆子移至 $4$，$a$ 环转到 $b$ 环，$b$ 环逆时针转一格，$b$ 环转到 $a$ 环。

G. Manhattan Walk

由于每个格子的状态是均匀独立随机的，并且到一个格子之前无法得知该格子的状态，因此可以看做到每个格子时再均匀随机状态。

设 $f(i,j)$ 表示从 $(i,j)$ 开始，到达终点的期望最小时间。如果 $i=r$ 或 $j=c$，则可以直接转移，否则设两个方向的 $f$ 值分别为 $a$ 和 $b$（$a\le b$）。

讨论两种情况：

• $b\ge a+p$，那么无论如何都会选择 $b$，期望为 $a+p/4$。
• $b < a+p$，那么只有当离能走 $a$ 还有超过 $b-a$ 的时间才会选择走 $b$，期望为 $(p-b+a)/2p\cdot b+a/2+(b-a)/2p\cdot (a+b)/2$。（三项分别代表选择走 $b$、可以走 $a$ 时走 $a$、等待后走 $a$ 的期望。）

时间复杂度 $O(rc)$。

H. MountainCraft

注意到斜线的长度等于横向覆盖的长度乘以 $\sqrt 2$。而横向覆盖的长度就是所有 $[x-y,x+y]$ 的并。使用线段树维护即可（维护区间最小值和最小值个数；或者因为减法只是加法的撤销，维护每个结点的覆盖次数）。

时间复杂度 $O(q\log q)$。

I. Not Another Constructive!

我们可以在字符 A 的位置计算贡献，也就是前缀中 N 的数量和后缀中 C 的数量的乘积。因此设 $f(i,N,C,k)$ 表示考虑了长度为 $i$ 的前缀，前缀中 N 的数量为 $N$，后缀中 C 的数量为 $C$，是否能恰好有 $k$ 个 NAC 子序列。可以用 bitset 优化。

时间复杂度 $O(n^3k/w)$。

J. Passport Stamps

第 $i$ 趟旅行可能无法进行的条件是 $p\le \sum_{j=1}^{i-1}c_j+i\cdot (c_i-1)$，也就是在前面每个章之间留恰好 $(c_i-1)$ 的间隔。

时间复杂度 $O(n)$。

注意，直接计算可能会超过 long long 的范围，需要使用 __int128 或改用除法。

K. Shadow Line

注意到要判断是否只有一片影子，只需要知道每个端点在墙上的位置的相对关系。而这些相对关系只会有 $O(n^2)$ 次变化，也就是在两两的连线与 $x$ 轴交点的位置。算出这些变化的位置之后就可以进行模拟。

只有一片影子的充要条件是对于每个真前缀，下端点的数量大于上端点的数量。因为每次都是交换位置相邻的端点，因此这个条件可以在 $O(1)$ 时间内维护。

要注意的细节包括在有三点共线时的交换顺序，以及 $x$ 轴上的下端点应该始终排在上端点之前。

时间复杂度 $O(n^2\log n)$。

L. Square of Triangles

M. Training, Round 2

设 $f(i,j,k)$ 表示考虑前 $i$ 个题，是否能恰好加 $j$ 次实现水平和 $k$ 次思维水平。注意这里当某个 $(j,k)$ 能达到时，之后都能达到。因此我们对每个 $j$ 维护两个集合：已经能达到的 $k$ 的集合以及已经更新过的 $k$ 的集合。对于每个问题，我们只需找到矩形中能达到但还未被更新过的 $(j,k)$，将 $(j+1,k)$ 和 $(j,k+1)$ 都加入能达到的集合。因为每个 $(j,k)$ 只会被更新一次，所以时间复杂度是 $O(n^2\log n)$。