February Challenge 2021 Division 1
Prime Game
结论：设前 (Y+1) 个小的质数的乘积是 (P)，若 (P|N)，那么先手胜，否则后手胜。
只需要考虑证明：从(P|N) 改一次一定到不整除的状态，从不整除的状态改一次可以到整除的状态，而 (0) 是整除的。"一定"显然，“可以”是因为我们选的是 (y+1) 个最小的质数，所以 (N\%P<P)，一定可以表示为 (<=y) 个质数幂次的乘积。
XOR Sums
考虑计算 (|S|=k) 的答案，是卷积的形式，(NTT/FFT) 搞一搞。
Multiple Games
根据 (A_1+A_ige A_{i+1}) 的性质，可以发现，在某局游戏中先手胜当且仅当 (M\%(A_l+A_r)ge A_l)。那么对 (A_l+A_r) 进行常规的根号分治。
Bash Matrix
基本的观察：对于最后停在起点位置的 ((i,j))，一定在一个环中；否则，假设它停在 ((x,y))，那么一定是先走到 ((x,y))，然后绕了一圈 ((x,y)) 所在的环。
更进一步：所有环都是偶环，我们可以把一个大环拆成若干个长度为 (2) 的小环，答案不会更劣（这样选择更多）。对于不在环上的，从 ((i,j)) 到 ((x,y)) 路径上的点应该都停在 ((x,y))。
对于不在环上的部分，可以通过从在环上的 ((x,y)) 开始跑最小树形图来确定答案。对于在环上的，将整个网格黑白染色，黑色的环上点放在左边，白的放在右边，然后跑一遍费用流即可。
Dream and the Multiverse
先用莫队转化为询问 ([1,i]) 内有多少点能到 (x)，(x) 能到 ([1,i]) 中的多少点，把这些询问二次离线。如果就一棵树，显然可以弄到dfs序上用数据结构解决，(O(n)) 次修改，(O(nsqrt{n})) 次询问。多了 (m) 条边后也类似，变为 (O(nm)) 次修改，(O(nsqrt{n})) 次询问。用普通线段树和普通的分块显然都不行。经过严密分析，使用 (n^{1/3}) 叉的线段树可以高效解决。