A. Coprime Array
注意到我们只关心 smod 的值(答案绝对值要求在 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)。