Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#234. Game Theory

统计

题目描述

给出长度为 $n$ 的 01 序列 $a_{1\sim n}$,序列中有偶数个 1。NIT 和 TIN 轮流做以下操作,NIT 先手:

  • 选择位置 $i\ (1\le i\le n)$,满足区间 $[1,i]$ 中有奇数个 1。再选择位置 $j\ (i\lt j\le n)$。将 $a_i,a_j$ 都取反(即,0110

当整个序列中的所有元素都变为 0 时,当前轮到的人就无法操作,他就输了。假设 NIT 和 TIN 都绝顶聪明,谁会赢?可以证明,游戏总会结束。

$n$ 可能很大,但序列中 $1$ 的个数不超过 $2\times 10^5$。

输入格式

本题有多组数据。

输入的第一行是数据组数 $T$。

接下来是每组数据的描述。每组数据的第一行是两个正整数 $n,m$,$m$ 为序列中 1 的个数,保证 $m$ 是偶数。

接下来一行 $m$ 个递增的正整数,描述这些 1 的下标,下标从 $1$ 开始。

输出格式

对每组数据,输出一行一个字符串 NITTIN,表示赢家的名字。

样例 #1

样例输入 #1

3
4 2
1 3
4 4
1 2 3 4
10 4
1 3 7 8

样例输出 #1

NIT
TIN
NIT

提示

样例解释

第一组数据中,NIT 选择 $i=1,j=3$ 就能把全部位置都变成 0,使得 TIN 无法操作。

第二组数据中,无论 NIT 先手怎么操作,都会剩下恰好两个 1 的位置。TIN 只需要选择这两个剩下的位置,就可以把全部位置都变成 0。

第三组数据中,一种可能的游戏进程如下(注意该进程里,每一步不一定是最优的):

  • NIT 选择 $i=2,j=3$ 并将这两个位置取反。现在 1 的位置在 $1,2,7,8$。
  • TIN 选择 $i=7,j=9$ 并将这两个位置取反。现在 1 的位置在 $1,2,8,9$。
  • NIT 选择 $i=1,j=5$ 并将这两个位置取反。现在 1 的位置在 $2,5,8,9$。
  • TIN 选择 $i=3,j=4$ 并将这两个位置取反。现在 1 的位置在 $2,3,4,5,8,9$。
  • NIT 选择 $i=4,j=5$ 并将这两个位置取反。现在 1 的位置在 $2,3,8,9$。
  • TIN 选择 $i=2,j=9$ 并将这两个位置取反。现在 1 的位置在 $3,8$。
  • NIT 选择 $i=3,j=8$ 并将这两个位置取反。现在序列里没有 1 了。
  • TIN 无法操作,NIT 获胜。

数据范围

对于所有数据,$1\le T\le 10^4$,$1\le n\le 10^{18}$,$2\le m\le 2\times 10^5$,$\sum m\le 10^6$。保证 $m$ 是偶数,保证为 1 的下标是递增顺序给出的。

  • 子任务 1($1$ 分)$T\le 10^3$,$n\le 10$。
  • 子任务 2($9$ 分)序列中全是 1
  • 子任务 3($40$ 分)$T\le 100$,$n\le 100$。
  • 子任务 4($10$ 分)$\sum n\le 10^6$。
  • 子任务 5($40$ 分)没有任何附加限制。