hdu5795 A Simple Nim 求nim求法，打表找sg值规律 给定n堆石子，每堆有若干石子，两个人轮流操作，每次操作可以选择任意一堆取走任意个石子（不可以为空） 或者选择一堆，把它分成三堆，每堆不为空。求先手必胜，还是后手必胜。

/**

题目：A Simple Nim

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5795

题意：给定n堆石子，每堆有若干石子，两个人轮流操作，每次操作可以选择任意一堆取走任意个石子（不可以为空）

或者选择一堆，把它分成三堆，每堆不为空。求先手必胜，还是后手必胜。

思路：

组合游戏Nim；

计算出每一堆的sg值，然后取异或。异或和>0那么先手，否则后手。

对于每一堆的sg值求解方法：

设：sg(x)表示x个石子的sg值。sg(x) = mex{sg(x-1),sg(x-2),...,sg(0),sg(a)^sg(b)^sg(c) |(a+b+c==x)}

当sg(0) = 0;

sg(1) = 1;

sg(2) = 2;

sg(x>=3)就要通过上面式子算出来了。

通过打表可以发现规律。

当x>=3.如果x是8的倍数，那么sg=x-1.

如果(x+1)是8的倍数，那么sg=x+1.

*/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<int,int> P;

const int maxn = 1e6+;

const int mod = 1e9+;

int T, n;

int main()

{

    cin>>T;

    while(T--)

    {

        scanf("%d",&n);

        int ans = ;

        for(int i = ; i < n; i++){

            int x;

            scanf("%d",&x);

            if(x%==&&x!=){

                ans ^= x-;

            }else

            {

                if((x+)%==){

                    ans ^= x+;

                }else

                {

                    ans ^= x;

                }

            }

        }

        printf("%s\n",ans?"First player wins.":"Second player wins.");

    }

    return ;

}

hdu5795 A Simple Nim 求nim求法，打表找sg值规律 给定n堆石子，每堆有若干石子，两个人轮流操作，每次操作可以选择任意一堆取走任意个石子（不可以为空） 或者选择一堆，把它分成三堆，每堆不为空。求先手必胜，还是后手必胜。的相关教程结束。