我们直接用二进制表示01串，对包含奇数个 1 的情况跑出 sg 函数（奇数的停止即为恰有一个 1 在末尾）。

我们观察到有$\operatorname{sg}(x)\oplus \operatorname{sg}(y)= \operatorname{sg}(x \oplus y)$。

我们观察到恰有一位为 1 的 sg 函数值在 n 是 2 的整数次幂的时候形成类似蝴蝶变换的优雅结构。具体地，对于 n=8，$T(1)-T(n)$为$\texttt{4,5,7,6,2,3,1,0}$，其中 $T(x)$ 表示恰好在第 x 位是 1，其他都是 0 的情况的 sg 函数值。

这个东西可以分治求单点值，通过了原题数据。

问题来了：

1. 以上的两个结论怎么证明？
2. 这与正解的做法有关联吗？

附上代码：

#include<iostream>
using namespace std;
#define ll long long
void read(ll &x){
	char ch=getchar();x=0;ll f=1;
	while(isdigit(ch)==0&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	x*=f;
}
ll ask(ll l,ll r,ll k,ll al,ll ar,bool tq){
	if(l==r)return al;
	ll mid=(l+r)>>1;
	ll md=(al+ar)>>1;
	if(k<=mid){
		if(!tq){
			return ask(l,mid,k,md+1,ar,!tq);
		}else{
			return ask(l,mid,k,al,md,tq);
		}
	}else{
		if(!tq){
			return ask(mid+1,r,k,al,md,tq);
		}else{
			return ask(mid+1,r,k,md+1,ar,!tq);
		}
	}
}
int main(){
	ll T;
	read(T);
	while(T--){
		ll ans=0;
		ll n,x;read(n);read(x);
		ll bj=1;
		while(bj<n){
			bj*=2;
		}
		for(int i=1;i<=x;i++){
			ll tq;
			read(tq);
			ll qwq=ask(0,bj-1,tq-1+bj-n,0,bj-1,0);
			ans^=qwq;
		}
		if(ans)cout<<"NIT\n";
		else cout<<"TIN\n";
	}
	return 0;
}