院科技文化节高级组 A. 是谁的猪蹄(SG打表)

思路来源

凯爷

题解

显然是一波SG函数的题，

然后1e9的话肯定会T，1e5的话没准还好点……

毕竟每个数都有因子1，会从1e9往下一直转移……

然后就T了GG

所以这题就是打表找规律

找出来的规律是，

SG值恰为该数能整除的2的最大幂次+1

心得

天天看逼乎上SG打表真到自己身上了不会打了……

感谢凯爷给我这么一个打表机会……

不然出去打不出来表都不好意思说自己学过博弈……

嗯，比赛时候记忆化搞错了把表打错了没找出来规律……

sg数组要赋-1啊 和sg[0]=0区别啊 辣鸡！！！

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=1e4+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int t,n,a[maxn],sg[maxn],hash[maxn];
/*
vector<int> divisor(int n)
{
	vector<int>ans; 
	for(int i=1;i*i<=n;++i)
	{
		if(n%i==0)
		{
			ans.push_back(i);
			if(i!=n/i)ans.push_back(n/i);
		}
	}
	return ans;
}
int getsg(int n)
{
	if(sg[n]!=-1)return sg[n];
	vector<int>p=divisor(n);
	int len=p.size();
	mem(hash,0);
	for(int i=0;i<len;++i)
	{
		hash[getsg(n-p[i])]=1;
	}
	for(int j=0;;++j)
	{
		if(!hash[j])return sg[n]=j;
	}
}*/
int getsg(int n)
{
	if(n==0)return 0;
	int res=1,num=1;
	while(n%(res*2)==0)res*=2,num++;
	return num;
}
int main()
{ 
   sci(t);
   mem(sg,-1);
   while(t--)
   {
   	sci(n);
   	rep(i,0,n-1)
   	{
   		sci(a[i]);
   	}
   	/*
   	for(int i=0;i<100;++i)
   	{
   		printf("%d:%d\n",i,getsg(i));
   	}*/
   	int ans=0;
   	rep(i,0,n-1)ans^=getsg(a[i]);
   	if(ans)puts("FEI!");
   	else puts("HANG!");
   }
   return 0;
}

/*
0:0
1:1
2:2
3:1
4:3
5:1
6:2
7:1
8:4
9:1
10:2
11:1
12:3
13:1
14:2
15:1
16:5
17:1
18:2
19:1
20:3
21:1
22:2
23:1
24:4
25:1
26:2
27:1
28:3
29:1
30:2
31:1
32:6
33:1
34:2
35:1
36:3
37:1
38:2
39:1
40:4
*/