2023湖南省赛-B Square game

思路：

（1）Nim游戏，考虑sg()函数，直接递归超时，于是打表找规律；

（2）发现只用算n^2与n^2加1项；于是预处理加异或即可

代码：

#include 
 
using namespace std;
 
typedef long long LL;
LL n,m;
 
const int N = 1e6 + 10;
 
LL f[N];
 
void sg()
{   	
	for(LL i = 1;i < N;i ++)
	{
		
		LL u = sqrt(i);
		LL v= sqrt(i - 1);
 
		if(u*u == i || v*v == i - 1)
		{
			unordered_set q;
		
			for(LL k = 0; k < i;k += u)
			{
				q.insert( f[k] );
			}
			
			for(LL j = 0;;j ++)
			 	if(q.count(j) == 0)
			 	{
			 		f[i] = j;
			 		break;
				 }
		}
		else
			f[i] = f[i - 1];
	}
}
 
int main() 
{
	int n;
	cin >> n;
	LL res = 0;
	
	sg();
	
	for(LL i = 0;i < n;i ++)
	{
		LL x;
		cin >> x;
		res^= f[x];
	}
 
		
	if(res == 0) puts("Second");
	else puts("First");
    return 0;
}