AtCoder arc208 总结

AtCoder arc208 总结

A

猜想 SG 是 \(a_1\oplus a_2\oplus \cdots \oplus a_n \oplus (a_1 \or a_2 \or \cdots \or a_n)\)。然后发现过了。

B

发现当 \(a_i=\lfloor\dfrac{a_{i+1}}2\rfloor +1\) 时 \(\sum (a_{i+1}-a_{i})\bmod a_i\) 可以取到最大，二分 \(a_n\) 的值即可。

注意二分的范围，不然会吃罚时。

C

可以记 \(n\oplus c=x+kn\)（\(k\ge 0\)），又想到 \(n\oplus c\le n+c\)，所以分类讨论：

• 当 \(c\le x\) 时，\(n\oplus c\le n+c\le n+x\)。所以分成两种情况：
  • \(n\oplus c =n+x\)，此时 \(c=x\)，此时 \(n=2^{59}\) 是合法解。
  • \(n\oplus c=x\)，则 \(n=c\oplus x\)。
• 当 \(c>x\) 时：
  • 发现当 __log(c)!=__log(x) 时，即最高位不同时，取 \(n=c\oplus x\) 是合法解。
  • 否则，打表出来前 \(500\) 个这种情况下的合法解，发现满足 \(n\oplus c =n+x\)，跑数位 DP 即可，具体地设 \(f_{i,0/1}\) 表示 \(n\) 的第 \(i\) 位取 \(0/1\) 时是否有解。

综上，只要 check \(c\oplus x\) 和 \(2^{59}\)，然后跑一遍数位 DP 即可，其他情况都是无解，复杂度 \(O(T\log V)\)。