数学问题 博弈 SG函数
我总觉得这题做过的……然而并没有记录
看上去是一个nim游戏的模型。
手推/打表找一下前几项的规律，发现x是偶数时，sg[x]=x/2，x是奇数时，sg[x]=sg[x div 2]
差点看漏了数据范围是1e18
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#define LL long long
using namespace std;
const int mxn=;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n;
LL SG(LL x){
if(x%==)return x/;
else return SG(x/);
}
int main(){
int i,j;LL x;
int T=read();
while(T--){
LL res=;
n=read();
for(i=;i<=n;i++){
x=read();
res^=SG(x);
}
if(res)printf("YES\n");
else printf("NO\n");
}
return ;
}