给出长度为 的
01
序列 ,序列中有偶数个1
。NIT 和 TIN 轮流做以下操作,NIT 先手:
- 选择位置 ,满足区间 中有奇数个
1
。再选择位置 。将 都取反(即,0
变1
,1
变0
)当整个序列中的所有元素都变为
0
时,当前轮到的人就无法操作,他就输了。假设 NIT 和 TIN 都绝顶聪明,谁会赢?可以证明,游戏总会结束。可能很大,但序列中 的个数不超过 。
01
序列的输入方式是 个递增的正整数,描述这些1
的下标,下标从 开始。,。保证 是偶数,保证为
1
的下标是递增顺序给出的。
妙妙题。
不难发现,操作相当于移动 。不妨设 ,游戏即转化为所有 均为 时无法操作。
-
的情况:
- ,相当于让 ;
- ,相当于让 ,;
-
的情况:
- ,相当于新建两个 和 ;
- ,相当于让 ;
下面将证明这个游戏等价于 Nim 游戏,即先手必胜当且仅当 。
设当前异或和为 ,则:
- 1.1 相当于 Nim 游戏的正常操作;
- 1.2 相当于让 ,由于存在 ,所以这两个在异或和中抵消了,相当于都变成了 ;
并且不难发现 “ 区间有奇数个 ” 这个限制是没有任何用的,因为 Nim 游戏中从 转移到 的操作方法是找到一个二进制最高位和 的最高位相同的 ,并让它减去 。设最大的满足条件的 为 ,则满足 的 一定有偶数个,那么此时操作 即可。
那么注意到 的情况已经涵盖了 Nim 游戏的所有合法操作,下面来证明 的情况不会出现。不难发现 的操作出现的目的一定是停在 的情况,那么只需要考虑操作产生的贡献有没有可能是 即可:
- 2.1 中 一定不等于 ,贡献一定不为 ;
- 2.2 中 贡献还是一定不为 ;
所以 的操作一定不会出现。
综上,证毕。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
const int S=200005;
int n,m;
int a[S];
inline void slove()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
int ans=0;
for(int i=1;i<=m;i++) ans^=n-a[i];
puts(ans==0?"TIN":"NIT");
}
int main()
{
int T;
scanf("%d",&T);
while(T-->0) slove();
return 0;
}