【题目来源】
【题目描述】
输入 k 及 k 个整数 n1, n2, …, nk，表示有 k 堆火柴棒，第 i 堆火柴棒的根数为 ni。接着便是你和计算机取火柴棒的对弈游戏。取的规则如下：每次可以从一堆中取走若干根火柴，也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：k=2，n1=n2=2，A 代表你，P 代表计算机，若决定 A 先取：
• A：(2,2)→(1,2)，即从第一堆中取一根。
• P：(1,2)→(1,1)，即从第二堆中取一根。
• A：(1,1)→(1,0)。
• P：(1,0)→(0,0)。P 胜利。
如果决定 A 后取：
• P：(2,2)→(2,0)。
• A：(2,0)→(0,0)。A 胜利。
又如 k=3，n1=1，n2=2，n3=3，A决定后取：
• P：(1,2,3)→(0,2,3)。
• A：(0,2,3)→(0,2,2)。
• A 已将游戏归结为 (2,2) 的情况，不管 P 如何取 A 都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取必败，如果是先取必胜，请输出第一次该如何取。如果是先取必败，则输出 lose。
【输入格式】
第一行，一个正整数 k。
第二行，k 个整数 n1，n2,，nk。
【输出格式】
如果是先取必胜，请在第一行输出两个整数 a，b，表示第一次从第 b 堆取出 a 个。第二行为第一次取火柴后的状态。如果有多种答案，则输出 <b, a> 字典序最小的答案（即 b 最小的前提下，使 a 最小）。
如果是先取必败，则输出 lose。
【输入样例一】
3
3 6 9
【输出样例一】
4 3
3 6 5
【输入样例二】
4
15 22 19 10
【输出样例二】
lose
【数据范围】
对于全部数据，k≤500000，ni≤10^9。
【算法分析】
● 经典 Nim 博弈定理：对于任意的 {a1, a2, a3, …, an}，若 S=a1⊕a2⊕a3⊕⋯⊕an 的值不等于 0，先手必胜，记为 N-position（先手必胜态）。若 S=a1⊕a2⊕a3⊕⋯⊕an 的值等于 0，先手必败，记为 P-position（先手必败态）。
● 根据经典 Nim 博弈定理，若要让对手进入必败态（P-position），需通过一步操作将总异或和 S=a1⊕a2⊕a3⊕⋯⊕an 变为 0。即若设对第 i 堆石子操作后，第 i 堆剩余的石子数量为 t，则此时对手进入必败态的条件为：a1⊕a2⊕⋯⊕t⊕⋯⊕an=0。
由于异或满足交换律 / 结合律，故可将上式变形，得：(a1⊕a2⊕⋯⊕ai⊕⋯⊕an)⊕ai⊕t=0，代入 S=a1⊕a2⊕⋯⊕an，得 S⊕ai⊕t=0。
由于异或满足性质（x⊕x=0 及 0⊕x=x），故可由 S⊕ai⊕t=0 推得第 i 堆剩余的石子数量 t=S⊕ai。进而可得，从第 i 堆拿走的石子数为 ai-S⊕ai。
● Nim 博弈的合法操作是从第 i 堆拿走若干石子（至少 1 个），即操作后第 i 堆剩余的石子数 t 需满足 0≤t<ai。结合上文结论 t=S⊕ai，可得“先手必胜”的充要条件为：S⊕ai<ai。
● 设 S=a1⊕a2⊕⋯⊕an，k 是 S 的二进制表示中「最左边的 1 所在的位置」。则在 a1，a2，⋯，an 中，只有满足第 k 位为 1 的 ai（其中，i∈[1~n]），才能通过合法操作（拿走若干石子），将总异或和变为 0，使对手进入必败态。
证明：要让对手必败，你必须做到两件事：
（1）有效：修改完 ai 后新的总异或和变成 0。
若要使总异或和变为 0，必须将 ai 改为 S⊕ai，无其他可能。
这是因为，设原来总异或和 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an，现在若只把 ai 换成一个新数 t，让新的总异或和等于 0（必败状态），即让 a1⊕a2⊕⋯⊕t⊕⋯⊕an=0。等价于，(a1⊕a2⊕⋯⊕ai⊕⋯⊕an)⊕ai⊕t=0，即 t=S⊕ai。
（2）合法：只能拿走石子，不能加。
由于 k 是 S 的二进制表示中「最左边的 1 所在的位置」，即最高位，所以这一位决定 S 的大小。
① 如果 ai 的第 k 位等于 1，则第 i 堆剩余的石子数量 t=S⊕ai 的第 k 位变成 1⊕1=0。则 t=S⊕ai 一定变小，即 t=S⊕ai<ai。显然，合法（拿走石子）且有效（异或和变 0）。
② 如果 ai 的第 k 位等于 0，则第 i 堆剩余的石子数量 t=S⊕ai 的第 k 位变成 0⊕1=1。则 t=S⊕ai 一定变大，即 t=S⊕ai>ai。显然，不合法（要加石子）、无效（最高位还是 1，异或和不可能为 0）。
● 为什么一定要从 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an 的二进制表示的「最左边的 1 所在的位置」开始判断？
答：设 k 是 S=a1⊕a2⊕⋯⊕ai⊕⋯⊕an 的二进制表示中「最左边的 1 所在的位置」。因为只有这一位，能保证第 i 堆剩余的石子数量 t=ai⊕S 与 ai 的大小关系绝对确定。原因是：
1. 若 ai 第 k 位等于 1，则 S⊕ai 的第 k 位等于 0 => S⊕ai<ai。
2. 若 ai 第 k 位等于 0，则 S⊕ai 的第 k 位等于 1 => S⊕ai>ai。
而在 k 右边的任意低位，都无法保证上述大小关系。
例如，S=3^6^9=12，对应的二进制为 1100。现在故意不用 S「最左边的 1 所在的位置」，改用 S「最右边的 1 所在的位置」，看会发生什么？
由于 S=3^6^9=12「最右边的 1 所在的位置」为 2（下标从 0 开始）。则：
3 = 0011 → 第 2 位 = 0
6 = 0110 → 第 2 位 = 1
9 = 1001 → 第 2 位 = 0
按上述规则，改第 2 位是 1 的堆，也就是 6 这堆，可得 12^6=10。
可见：10>6 → 要加石子，非法！
● 异或运算的基本性质（）
异或运算（XOR）具有以下重要性质：
交换律：a ^ b = b ^ a
结合律：a ^ (b ^ c) = (a ^ b) ^ c
自反性：a ^ a = 0
零元素：a ^ 0 = a
可逆性：如果 a ^ b = c，那么 a = c ^ b
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=5e5+5;
int a[N];
int n;int main() {int s=0;cin>>n;for(int i=1; i<=n; i++) {cin>>a[i];s^=a[i];}if(s) {int k=0;//Find left-most bit '1' in binary of sfor(int i=31; i>=0; i--) {if(s>>i & 1) {k=i;break;}}//Find 1st stone heap where k-th bit is '1'for(int i=1; i<=n; i++) {if(a[i]>>k & 1) {cout<<a[i]-(s^a[i])<<" "<<i<<endl;//remaining stones in i-th pile is s^a[i]a[i]=s^a[i];break;}}for(int i=1; i<=n; i++) cout<<a[i]<<" ";} else cout<<"lose\n";return 0;
}/*
in:
3
3 6 9out:
4 3
3 6 5
*/
【参考文献】