比 ARC184 简单多了。
A. mod M Game 2
我们只关心 Alice 出的最后一张牌，这张牌会决定游戏的胜负，因为除了最后一张牌，二人都可以选择出牌来使得自己不会输。
让我们假设 Alice 最后出的牌为 \(x\)，那么在打出最后一张牌之前的牌之和为 \(n(n-1)-x\)。
- 若 \([n(n-1)-x]\bmod m=0\)，令 \(y=n(n-1)\bmod m\)，如果 Bob 打出的前 \(n-1\) 张牌中没有 \(y\)，那么 \(x=y\)，此时 Alice 会输。可以被证明，Bob 一定存在一种策略能够达到这种状态。
- 若 \([n(n-1)-x]\bmod m\not=0\)，此时 Alice 必胜。
条件 1 就等价于 \(1\le n(n-1)\bmod m\le n\)。
B. +1 and -1
贪心的想，我们想尽量让最后的 \(A\) 中的元素尽量接近（平均值），令 \(s=\sum A_i\)，那么最终的序列 \(A=(\lfloor \frac{s}{n}\rfloor,\lfloor \frac{s}{n}\rfloor,\dots,\lfloor \frac{s}{n}\rfloor+1,\dots,\lfloor \frac{s}{n}\rfloor+1)\)，其中 \(\lfloor \frac{s}{n}\rfloor+1\) 共有 \(s\bmod n\) 项。
之后我们就只需要判断 \(A\) 是否可能通过操作变成上述的样子，这是容易的。
详细证明可以见 Atcoder 官解。
C. Sum of Three Integers
题目只要求给出任意一组合法解。
让我们枚举 \(i=1,2,\dots,n\)，之后我们就只需要判断是否有两个整数 \(j,k\) 满足 \(A_j+A_k=X-A_i\)。
我们可以通过一次卷积来解决这个问题。
具体的，我们可以通过一次卷积求出有多少个 \(A_j+A_k(1\le j,k\le n)\) 等于某个值 \(Y\)，但是可能 \(j=k\)，此时将每一个 \(A_p+A_p\) 的方案减去一。
除此之外，还可能存在 \(A_i+A_k=X-A_i\) 也就是一个 \(A_i\) 出现两次的情况，我们可以先提前预处理出满足这种情况的方案数，最后在减去即可。
时间复杂度 \(O(X\log X)\)。
D. Random Walk on Tree
没有场切。
先让我们考虑 \(m=1\) 的情况。
此时 Takahashi 会在节点 \(0\) 和一个叶子节点之间反复移动，显然，Takahashi 想要给这 \(n\) 个叶子节点都染上色的期望往返次数为 \(\sum_{i=0}^{n-1}\frac{n}{n-i}\)，每次往返需要 \(2\) 步，且最后一次不需要往返，所以期望步数为 \(2(\sum_{i=0}^{n-1}\frac{n}{n-i})-1\)。
接下来让我们单独考虑一条长度为 \(m\) 的链的情况，转化为这样一个问题：初始时 \(i=0\)，每次随机将 \(i\) 变为 \(i+1\) 或 \(i-1\)，当 \(i=0\) 时只有第一种操作，求出 \(i\) 变为 \(m\) 的期望操作次数。
令 \(f_i\) 表示将 \(i\) 变为 \(i+1\) 的期望次数，令 \(g_i\) 表示将 \(i+1\) 变为 \(i\) 的期望次数，我们有：
- 当 \(i=0\) 时，有 \(f_0=g_0+1\)。
- 当 \(i=m-1\) 时，有 \(f_{m-1}=0,g_{m-1}=1\)。
- 当 \(1\le i\le m-1\) 时 \(f_i+g_{i-1}=f_{i+1}+g_i\)，因为中间所有点的期望进出次数是相同的。
若我们固定了移动的起点，在每一个点时它进行两种操作的概率时相同的，所以进行操作的期望次数与它具体是那种操作无关，于是有 \(f_i=g_{i-1}\)。
从大到小考虑每个点，有 \(f_i=m-i,g_i=m-i-1\)，所以总期望次数为 \(m^2\)。
最后的答案就是 \((2(\sum_{i=0}^{n-1}\frac{n}{n-i})-1)m^2\)。
E. Adjacent GCD
依次枚举每一个 \(m=i=1,2,\dots n\) 来求解答案，记 \(m=i\) 的答案为 \(ans_i\)。
在我们不考虑 \(i\) 时，答案为 \(2ans_{i-1}\)。
现在让我们考虑 \(i\)，记子序列中的上一个选择的数为 \(j\)，那么最新造成 \(\gcd(a_i,a_j)2^{j-1}\) 的贡献。
也就是说 \(ans_i=2ans_{i-1}+\sum_{j=1}^{i-1}\gcd(a_i,a_j)2^{j-1}\)。
现在让我们考虑后面那一坨玩意。考虑求出每个 gcd，然后再乘上 \(2^{j-1}\)，但这样算肯定不对，因为我们无法确定这个就是那两个数的 gcd，无法保证它们没有其它的质因子。
但是，我们知道 \(x=\sum_{d\mid x}\varphi(d)\)。
也就是说，我们只需要枚举 \(a_i\) 的每个因子 \(p\)，看有多少个数包含这个因子 \(p\)，那么这个因子对答案造成的贡献就为 \(p\cdot\varphi(p)\)。
时间复杂度 \(O(n\sqrt{a_i})\)。
