AtCoder Regular Contest 185
保龄选手来写下记录。
A
由于 \(N < M\)，所有 \(i\) 在模 \(M\) 意义下互不相同。
这说明如果一个人至少有两张牌，当前回合一定不会输。
设 \(b\) 为 Bob 的最后一张牌。
Alice 打出最后一张牌后局面达到 \(N(N + 1) - b\)。当且仅当 \(b \equiv N(N + 1) \pmod M\)，Bob 胜。
设 \(c = N(N + 1) \bmod M\)
-
\(c \in [1, N]\)。
如果 Bob 一直将 \(c\) 保留到最后，他就赢了。
-
Bob 手中牌数 \(\ge 3\)。
可以用除 \(c\) 外的另外两张来保证自己不会输。
-
Bob 手中牌数等于 \(2\)。
设 Alice 打出最后一张牌为 \(a\)。
则 Bob 倒数第二轮不打 \(c\) 能达到的局面为 \(N(N + 1) - a - c \equiv -a\not\equiv 0\)，不会输。
-
-
\(c \notin [1, N]\)，无论如何 Bob 都不会赢。
submission
B
定义一个非降序列是「好的」当且仅当序列极差不大于 \(1\)。
结论：答案合法当且仅当他能操作为一个好的序列。
充分性：好序列也是非降的。
必要性：任意非降序列都能操作为一个好序列：
- 每次找到靠的最近 \(i < j\) 满足 \(A_j - A_i \ge 2\)，一定有 \(A_i < A_{i + 1}\)，否则 \(i + 1\) 更靠近 \(j\)，同理 \(A_{j - 1} < A_j\)。
- 操作后仍然满足 \(A_{i}^{\prime} \le A_{i + 1} \le \cdots \le A_{j - 1} \le A_j^{\prime}\)。
- 不断操作直到找不到 \(i, j\)（极差不大于 \(1\)）。
最后能转化为的好的序列是唯一确定的，设为 \(B\)。
非法当且仅当存在 \(\sum_{j = 1}^iA_i > \sum_{j = 1}^iB_i\)：
一次操作 \(i, j\) 会使 \([i, j)\) 的前缀和加一，\((j, n]\) 的前缀和不变，即始终满足 \(\forall i,\ B_i \ge A_i\)。
必要性显然，考虑充分性。
不妨将一次操作当成 \(B\) 前缀和上的区间加，如果任意 \(B_i \ge A_i\)，最朴素的构造即对 \((i, i + 1)\) 操作 \(B_i - A_i\) 次。
submission
C
记 \(f(x) = \sum [A_i = x],\ g(x) = \sum[i < j \land A_i + A_j = x]\)。
\(g\) 可以通过 \(f * f\) 再减掉点东西得到。
枚举 \(1 \le i \le n\)，判断是否存在 \((j, k),\ j < k\) 对使得：
- \(i \ne j \land i \ne k\)。
- \(A_i + A_j + A_k = X\)。
一旦我们知道 \((j, k)\) 是否存在，即可用 \(O(N)\) 的时间找到一组解（枚举 \(j\)，至多枚举三个 \(A_k = X - A_i - A_j\)）。
考虑计算 \((j, k)\) 的个数：
即所有 \(j < k,\ A_j + A_k = X - A_i\) 的方案减去 \(i\) 为其中之一的方案。
时间复杂度 \(O(N + V\log V)\)。（NTT模数取1374389534721）
submission
D
E
首先有朴素 DP：
注意到
\(f\) 部分先不管，最后加一个前缀和即可：
同时维护 \(g(d) = \sum_{d\mid a_j} 2^{j - 1}\)，时间复杂度 \(O(V\ln V + Nd(V))\)。
submission