第一周

Giant Graph

首先 \(10^{18}\) 很大，所以我们优先选取 \(x+y+z\) 最大的点。

按 \(x+y+z\) 从大到小选择即可。

但是时间复杂度为 \(\mathcal O(n^3)\)。

给边定向，边从小连到大，那么整个图就是一个 DAG。

发现对于每个点 \(i\):

• 如果 \(i\) 的出边被选了，则不能选择 \(i\)。
• 如果都不能被选或者 \(i\) 没有出边，选择 \(i\)。

这和博弈转移一模一样。

答案为必败点的权值和。

容易发现每一张图都是独立的（每次相当于换一张图或者说换一维操作），SG 记为 \(A_{0,i}\)，\(A_{1,i}\)，\(A_{2,i}\)。

则答案为 \(\sum_{A_{0,i}\operatorname{xor} A_{1,j}\operatorname{xor} A_{2,k}=0} 10^{18(i+j+k)}\)。

同时有一个很重要的性质：博弈转移图中的点的 SG 值的 \(\max\) 不会超过 \(2\sqrt m\)，Proof。

于是枚举 \(A_{0,i},A_{1,j}\) 即可。

时间复杂度 \(\mathcal O(n+m)\)。

Submission。

Easy

一句话题解：判断不同元素的奇偶性。

Proof：

显然，对于 \(x\ne y\)，\((x\operatorname{xor} z)\ne (y\operatorname{xor} z)\)。

若我们连续操作 \(x,y\)，则发现 \(x\) 的影响被全部消除。

则每次可以消除一种相同元素。

Midium

首先记 \(s_i=\sum_{i=1}^i a_i\)。

所有序列都可以表示为 \(s_i-s_{j-1}\)。

因此可以处理所有 \(-s_i\)，处理负数下标，bitset 优化即可。