推导过程
这是经典 Nim 游戏模型。
这个游戏的 SG 值就是各堆数量的异或和，当 SG 为 (0) 时先手必败，否则先手就要把 SG 变为 (0)。
先检验 SG 值，如果是 (0) 输出 lose，否则我们按照以下原则行动：
有 (n) 个数的异或值不为 (0)，现在要减少一个数使异或值为 (0)。
假设 (n) 个数：(a_1,a_2,dots,a_n)，且 (a_1operatorname{xor}a_2operatorname{xor}dotsoperatorname{xor}a_n=k)，那么我们可以对一个数进行操作。
假设这个数是 (a_i)，设 (a_ioperatorname{xor}k=a')，则：
[egin{align*}
&a'operatorname{xor}a_1operatorname{xor}a_2operatorname{xor}...operatorname{xor}a_{i-1}operatorname{xor}a_{i+1}operatorname{xor}dotsoperatorname{xor}a_n\
&=a_1operatorname{xor}a_2operatorname{xor}a_3operatorname{xor}...operatorname{xor}a_noperatorname{xor}k\
&=koperatorname{xor}k\
&=0
end{align*}
]
所以我们只需要从头到尾检验每个数异或 (k) 的值是否比它小(因为是要减少)，遇到小的直接输出 (a_i-a_ioperatorname{xor}k) 即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
int main() {
int n;
scanf("%d",&n);
int x=0;
for(int i=1; i<=n; i++) {
scanf("%d",a+i),x^=a[i];
}
if(!x) {
puts("lose");
return 0;
}
for(int i=1; i<=n; i++) {
if((a[i]^x)>=a[i]) {
continue;
}
printf("%d %d
",a[i]-(a[i]^x),i),a[i]^=x;
break;
}
for(int i=1; i<=n; i++) {
printf("%d ",a[i]);
}
return 0;
}
