题意

有n堆石头，每堆石头有个石子，玩家双方轮流取石子，每次可以选择一堆石子取该石子数量二进制子集中任意一元素大小数量的石子，例如对应子集为，所以可以取走11或10或9或8等等数量的石子。现在给你n堆石子的数量请你告诉谁能必胜呢。

思路

标准nim博弈可以用sg函数来进行异或。由于较大所以是个找规律的题目。枚举二进制子集可以用状压dp的方式来枚举该子集

for(int i=a;i!=0;i=(i-1)&a)

那么我们可以得到sg函数为

const int N=1e3+5;
int vis[N];
int sg[N];
void get_SG(int n)
{
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=i;j!=0;j=(j-1)&i)
            vis[sg[i-j]]=1;
        for(int j=1;j<=n;j++)
            if(vis[j]==0)
        {
            sg[i]=j;
            break;
        }
    }
}

进行打表有

1 1
2 1
3 2
4 1
5 2
6 2
7 3
8 1
9 2
10 2
11 3
12 2
13 3
14 3
15 4
16 1
17 2
18 2
19 3
20 2

可以发现sg[i]的值就是其二进制下1的个数那么我们只要将每个二进制1的个数异或起来，若其值为0则先手必败，反之则必胜。可以用__builtin_popcount()函数来获取二进制下1的个数。

代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return string字符串
     */
    string StoneGame(int n, vector<int>& a) {
        // write code here
        int ans=0;
        for(int i=0;i<n;i++)
            ans^=__builtin_popcount(a[i]);
        if(ans==0)
            return "NiuNiu";
        else
            return "NiuMei";
    }
};