abc313D 题解

[abc313D Odd or Even]。

好有趣捏。

我们考虑 \(N=K+1\)。

设 \(s_i\) 为 \(\displaystyle\sum_{j\neq i}a_j\bmod 2\)。

因为 \(K\) 为奇数，我们可以得到 \(\displaystyle\sum_{i=1}^{K+1}s_i\equiv\sum_{i=1}^{K+1}a_i\pmod2\)。

所以 \(a_i=\displaystyle\sum_{i=1}^{K+1}a_i\bmod 2-s_i\)，即 \(a_i=\displaystyle\sum_{i=1}^{K+1}s_i\bmod 2-s_i\)。

我们考虑 \(N\neq K+1\) 的情况。

我们先用 \(N=K+1\) 的做法求出 \(a_{1\sim K+1}\)，然后对于 \(\forall i\in[K+2, N]\)，询问 \(\{1, 2,\cdots, K-1, i\}\)，即可得到 \(a_i\)。

时间复杂度：\(\mathcal O(n^2)\)。

代码。