Nim or not Nim?

2
3
2 2 3
2
3 3

Alice
Bob

题目大意：

Alice和Bob轮流取N堆石子，每堆S[i]个，Alice先。每一次能够从随意一堆中拿走随意个石子，也能够将一堆石子分为两个小堆。先拿完者获胜。

(1 ≤ N ≤ 10^6, 1 ≤ S[i] ≤ 2^31 - 1)

对于一个给定的有向无环图。定义关于图的每一个顶点的Sprague-Grundy函数g例如以下：g(x)=mex{ g(y) | y是x的后继 },这里的g（x）即sg[x]
比如：取石子问题，有1堆n个的石子，每次仅仅能取{1。3,4}个石子。先取完石子者胜利。那么各个数的SG值为多少？
sg[0]=0,
n=1时，能够取走{1}个石子，剩余{0}个。mex{sg[0]}={0}。故sg[1]=1;
n=2时，能够取走{1}个石子。剩余{1}个，mex{sg[1]}={1}。故sg[2]=0；
n=3时。能够取走{1,3}个石子，剩余{2,0}个。mex{sg[2],sg[0]}={0,0}，故sg[3]=1;
n=4时，能够取走{1,3,4}个石子。剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
n=5时。能够取走{1,3,4}个石子。剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3；
以此类推.....
     x  0  1  2  3  4  5  6  7  8....
sg[x] 0  1  0  1  2  3  2  0  1....

所以，对于这题：

sg[0]=0

sg[1]=mex{sg[0] }=1

sg[2]=mex{sg[0],sg[1],sg[1,1] }=mex{0,1,1^1}=2;

sg[3]=mex{sg[0],sg[1],sg[2],sg[1,2]}=mex{0,1,2,1^2}=mex{0,1,2,3}=4;

sg[4]=mex{sg[0],sg[1],sg[2],sg[3],sg[1,3],sg[2,2]}=mex{0,1,2,4,5,0}=3;

              ..............................................................................

能够发现：sg[4*k+1]=4*k+1,sg[4*k+2]=4*k+2,  sg[4*k+3]=4*k+4,sg[4*k+4]=4*k+3

解题代码：

#include <iostream>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t-- >0){
        int sg=0,n,x;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>x;
            if(x%4==0) sg^=x-1;
            else if(x%4==3) sg^=x+1;
            else sg^=x;
        }
        if(sg) cout<<"Alice"<<endl;
        else cout<<"Bob"<<endl;
    }
    return 0;
}