A - mod M Game 2
第一个观察是如果一个人手中还有 2 张牌，那么他一定不会被秒。
这可以推出决定胜负的时刻一定是 Alice 和 Bob 手中只剩一张牌的时候，此时如果 Alice 被秒了，那么她就似了，否则她就赢了。
考虑 Alice 什么时候能被秒。记决定胜负的时刻 Alice 手中的牌是 \(a\)，Bob 手中的牌是 \(b\)，那么 Alice 被秒的必要条件就是 \(b \equiv N (N + 1) \pmod M\)，不妨去证明它也是充分的。
- 若 \(1 \le N(N + 1) \bmod M \le N\)，此时 \(b = N(N + 1) \bmod M\)。当 Bob 有 \(\ge 3\) 张牌时，他可以留着 \(b\) 这张牌不出；当 Bob 有恰好 2 张牌时，若 Bob 留着 \(b\) 不出，那么此时牌的和为 \(N(N + 1) - a - b\)，不难发现它一定不会是 \(M\) 的倍数，所以 Bob 可以留着 \(b\) 不出。由此可知，Bob 一定能赢。
- 否则，Bob 一定输。
可以 \(O(1)\) check。
B - +1 and -1
关键性质：操作不会改变数列的和。
记 \(sum = \sum_{i} A_i\)。
我们可以构造一个新序列 \(A'\)，满足 \(\forall i \in [1, n - sum \bmod n], A'_i = \lfloor sum / n \rfloor\)，\(\forall i \in [n - sum \bmod n + 1, n], A'_i = \lceil sum / n \rceil\)。
大胆猜测，如果 \(A\) 能调整成不降的序列，那么 \(A\) 一定能调整成 \(A'\)。
这显然是正确的，因为我们可以对 \(A\) 调整成的不降的序列贪心调整。
所以只需要 check \(A\) 是否能调整成 \(A'\) 即可，这个可以贪心判断。
时间复杂度 \(O(n)\)。
C - Sum of Three Integers
枚举 \(i\)，然后就转化成了寻找 \(j, k\) 使得 \(a_j + a_k = X - a_i\)。
先考虑如何判断可行性。
记 \(F(x) = \sum_{i = 1}^n x^{a_i}, G(x) = F^2(x) - \sum_{i = 1}^n x^{2a_i}\)，那么 \([x^{X - a_i}] G(x)\)，就是 \(j, k\) 的方案数。
然后暴力判断即可，注意实现，不要多次进循环。
时间复杂度 \(O(V \log V + n)\)。
D - Random Walk on Tree
先考虑 \(m = 1\) 的情况，此时图是一个菊花。
我们走过的路一定是从 0 走到叶子，然后再返回根，记这为一次 round trip。
考虑如果已经染了 \(i\) 个叶子，此时还需要的 round trip 次数为 \(\frac{N}{N - i}\)。
所以答案为 \(2 \cdot\big(\sum_{i = 0}^{N - 1} \frac{N}{N - i} \big) - 1\)（最后一次到叶子无需返回）。
对于 \(m \ge 1\) 的情况，发现一次 round trip 的期望步数为 \(2m^2\)（多分支不影响 round trip 的步数），那么可以得到答案为 \(m^2\) 乘上 \(m = 1\) 的答案。
时间复杂度线性。
E - Adjacent GCD
考虑从小到大枚举 \(i\)，计算答案的变化量。
首先原本的答案会乘 2，因为可以把原本的 \(A_i\) 状态取反形成新的状态。
然后要计算 \(A_i\) 的贡献，即 \(\sum_{j < i} 2^{j - 1} \gcd(A_j, A_i)\)。
考虑维护每个值的贡献系数 \(k_i\)，那么就转化为了求：
\[\sum_{i = 1}^n k_i \cdot \gcd(i, x) \]直接上欧拉反演：
\[\begin{aligned} &\sum_{i = 1}^n k_i \cdot \gcd(i, x) \\ = \ & \sum_{i = 1}^n k_i \cdot \sum_{d \mid \gcd(i, x)} \varphi(d) \\ = \ & \sum_{d \mid x} \varphi(d) \cdot \sum_{d \mid i} k_i \end{aligned} \]这样就能做到 \(O(n \cdot d(n))\) 了。
标签：AtCoder,cdot,题解,sum,Alice,185,bmod,Bob,round From： https://www.cnblogs.com/definieren/p/18500275