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