$\rm{Description}$

给定数列 $n_1, n_2, \cdots, n_k$，表示有 $k$ 堆物品，第 $i$ 堆物品的数量为 $n_i$。

两人轮流从中取物品，规则：每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。

对于给定的数列，判断先手是否必胜，若必胜，输出第一次应该在哪堆取多少物品。

$\rm{Solution}$

必胜必败分析

先手必胜，当且仅当 $n_1\oplus n_2\oplus\cdots\oplus n_k\neq 0$。

对于其他 nim游戏 ，假设状态表示为 $(a_1, a_2, \cdots,a_n)$，那么先手必胜，当且仅当 $\operatorname{sg}(a_1)\oplus \operatorname{sg}(a_2)\oplus\cdots\oplus \operatorname{sg}(a_n)$，证明BFS。

本题中 $\operatorname{sg}(i)=i$，所以有上面的结论。

证明

设 $s=n_1\oplus n_2\oplus\cdots\oplus n_k$.

也就是证明：

1. 当 $s \neq 0$ 时，存在一种取法，使得 $s=0$.
2. 当 $s=0$ 时，无论怎么取物品，$s$ 都不等于 $0$.

命题一

因为 $s\neq 0$，根据异或的定义，存在一堆物品 $i$，满足 $n_i\oplus s

此时，$s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_k\oplus s=s\oplus s=0$.

所以命题一成立。

命题二

反证法。若否，则 $s=0$ 时，存在一种取物品的方法使得 $s_{\rm{new}}=0$.

设取走第 $i$ 堆的若干物品，第 $i$ 堆剩余 $n_i’$ 个物品。

所以 $s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_i’\oplus\cdots\oplus n_k=0=s$.

把 $s$ 的定义式代入，得到 $n_i=n_i’$，产生矛盾。

所以命题二成立。

找方案的方法

利用命题一。找到一堆 $i$，满足 $n_i\oplus s < n_i$，将这一堆拿走 $n_i-(n_i\oplus s)$ 个物品，使得新的异或和为 $0$，满足题意。

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000008;
int T, n;
int a[MAXN];
int main() {
    scanf("%d", &n);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        res ^= a[i];
    }
    if(res == 0) {
        cout << "lose" << endl;
    } else {
    	for(int i = 1; i <= n; i++) {
    		if((res ^ a[i]) < a[i]) {
    			cout << a[i] - (res ^ a[i]) << " " << i << endl;
    			a[i] = res ^ a[i];
    			break;
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    return 0;
}