LA 5059博弈+SG函数

 1 /*UVALive 5059
 2 建立 SG函数：
 3 单堆：每次拿走至少一个石子，不能拿走超过一半的石子；
 4 边界：SG[1]=0;
 5 公式：SG[X]=MEX{SG[X-1],SG[X-2]....，SG[x-x/2]}
 6 测试：
 7 
 8 int SG[105],vis[105];
 9 int main()
10 {
11     memset(SG,-1,sizeof(SG));
12     SG[1]=0;
13     for(int i=2;i<=100;i++)
14     {
15         memset(vis,0,sizeof(vis));
16         for(int j=i-i/2;j<=i-1;j++) vis[SG[j]]=1;
17         for(int j=0;j<=100;j++) if(!vis[j]) {SG[i]=j;break;}
18     }
19     for(int i=1;i<=20;i++) cout<<SG[i]<<"　";
20     //ans=0　1　0　2　1　3　0　4　2　5　1　6　3　7　0　8　4　9　2　10　
21 }
22 拓展公式：
23 SG[X]=X/2，X为偶数
24 SG[X]=SG[X/2],X为奇数，向下取整
25 */
26 
27 #include<iostream>
28 #include<stdio.h>
29 #include<string.h>
30 #include<algorithm>
31 #include<stdlib.h>
32 #include<math.h>
33 #include<queue>
34 #include<vector>
35 #include<map>
36 
37 using namespace std;
38 
39 long long SG(long long x)
40 {
41     return x%2==0?x/2:SG(x/2);
42 }
43 int main()
44 {
45     int t;
46     cin>>t;
47     while(t--)
48     {
49         long long  v=0,n,a;
50         cin>>n;
51         for(int i=0;i<n;i++){
52             cin>>a;v^=SG(a);
53         }
54         if (!v) cout<<"NO"<<endl;else cout<<"YES"<<endl;
55     }
56 }