AtCoder Regular Contest 131

C. Zero XOR

结论：

1. \(2\not|n\)时，必胜。

2. \(2|n\)时，若存在\(XORSUM=A_i\)，则必胜，否则必败。

证明：

只需证明1即可。

转化：证明1，只需证明\(n\)为奇数时，游戏不会在恰好2次操作后结束。

若游戏在两轮后一定结束，则\(\forall A_i, \exists A_{p_i}\ s.t.\ S \oplus A_i \oplus A_{p_i}=0\)

则所有\((i,p_i)\)组成\(n/2\) 组。而必然剩余一组\(p_i=i\)，构成矛盾。

D. AtArcher

1. 距离必定\(=d\)

2. 中点必定在0附近

3. 中点最多移动\(O(d)\)，而所有所属区间的变化数量为\(O(m)\)

4. 线性扫描即可

E. Christmas Wreath

思路：先判定有解后构造/优先考虑特殊限制

有解条件

\(n \not=2(mod\ 3)\)

考虑如何满足条件2

    如果每一个点的邻接边都同色，则条件2必然满足。

问题转化为：将\(1,2,3\dots n-1\)分成和相等的三组。

增量构造即可。