竞赛
考级
zsy
根据 Nim\text{Nim}Nim 博弈的性质可知: * 当异或和为 000 时,先手必败。 * 当异或和不为 000 时,先手必胜,只要在某一堆取出一定量的石子使异或和为 000 即可。 记 AAA 数组异或和为 XXX,则答案为 ∑i=1n[X⊕Ai≤Ai]\sum_{i=1}^n [X\oplus A_i\le A_i]∑i=1n [X⊕Ai ≤Ai ]。显然可以 O(N)O(N)O(N) 求出。 当然,如果 X=0X=0X=0,记得特判输出 000。
复仇者_帅童
Nim板子题,不做解释,如有疑问请百度/洛谷题解。 Code:
亚洲卷王 AK IOI