在Nim游戏中，限定第一回合玩家可以拿走任几堆石子，但不能全部拿完，同样第二回合选手进行同样操作，接下来的回合同Nim游戏操作，询问先手是否必胜所拿走的最少的石子。

解

不难得知应该要用Nim游戏的结论，自然想到暴力建SG函数，但是注意问题只有前两个回合特殊，根据Nim定理，换一种解释即选出最多的数构成一个集合，使其任意子集异或和不为0。

异或和问题，考虑线性基，现在我们有了如何判断异或和是否为0的工具，经验告诉我们自由选择一般不能递推，于是考虑贪心，从大到小选择，如果能够加入线性基，就选择即可，正确性证明如下。

---

证明：

假设选到第i个数\(a_i\)，前i个数已经选到最优情况，如果不是最优的情况，必然至少存在\(a_j,a_k\)使其和大于\(a_i\),并且因为\(a_i\)的存在，不能加入线性基，但是\(a_i\)在线性基中只占一个二进制位，而因为其存在而不能选这两个数，意味着这两个数加入线性基时必然也占这一个二进制位，而位置只有一个，故显然它们会互斥，于是矛盾，得证。

---

参考代码：

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define ll long longusing namespace std;struct linear_base{    int base[32];    il bool insert(int x){        ri int i;        for(i=31;i>=0;--i)            if(x>>i){                if(base[i])x^=base[i];                else return base[i]=x;            }return false;    }}B;int a[101];il void read(int&);int main(){    int k,i;ll ans(0);read(k);    for(i=1;i<=k;++i)read(a[i]);sort(a+1,a+k+1);    for(i=k;i;--i)if(!B.insert(a[i]))ans+=a[i];    printf("%lld",ans);    return 0;}il void read(int &x){    x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();}