注：本篇题解为半萌新向，

知道什么是 nim 游戏的跳到第二章；

知道什么是阶梯 nim 的跳到第三章；

只是想看代码的去第四章；

一：nim 游戏

nim 游戏规则： 有 $n$ 堆石子，数量分别为 $a_1,a_2,a_3,\cdots,a_n$。 两个玩家轮流拿石子，每次从任意一堆中拿走任意数量的石子，拿到最后一个石子的玩家获胜。

如何判断胜负？对于任意的 $a_1,a_2,a_3,\cdots,a_n$，nim 游戏有一个很简单的判断胜负的方法。

定理1：

若 $a_1 \operatorname{xor} a_2 \operatorname{xor} a_3 \operatorname{xor} \cdots \operatorname{xor} a_n = 0$，则先手必败。

若 $a_1 \operatorname{xor} a_2 \operatorname{xor} a_3 \operatorname{xor} \cdots \operatorname{xor} a_n \neq 0$，则先手必胜。

在 nim 游戏中进行的异或运算一般被称为 Nim-sum 运算。

下面对该定理进行简单证明：

1. 若先手处于必胜点，则先手必然可以将局势转化为必败点。为什么？我们任选一堆石头，例如第 $i$ 堆，石头数量为 $a_i$；对剩下的 $n-1$ 堆进行异或运算，设结果为 $H$。若 $H < k$，就把第 $i$ 堆石头减少到 $H$ 个。因为 $H \operatorname{xor} H = 0$，所以这样操作以后 $n$ 堆石头的异或等于 $0$。可以证明，总会存在这样的第 $i$ 堆石头。

2. 若先手处于必败点，则先手必然只能转移到必胜点。因为先手不论取哪堆，取多少，都会使得这一堆的二进制表达至少产生一位不同，导致异或值改变。

3. 当所有石子取完时，显然为先手必败点（可以看作后手在上一轮取走了最后一个石子），又所有石头此时异或值为 $0$，证毕。

二：阶梯 nim 游戏

阶梯 nim 规则：

有 $n$ 堆石子，数量分别为 $a_1,a_2,a_3,\cdots,a_n$。 两个玩家轮流进行以下操作：

1. 从第 $i$ 堆石子中移动任意颗石子到第 $i - 1$ 堆中（$i \ge 2$）。
2. 从第一堆石子中移除任意颗石子。

这东西和 nim 游戏有啥关系啊？

关系就在：

定理二：

阶梯 nim 的结果与只看奇数堆的普通 nim 是一样的。

证明如下：

1. 若对手将奇数堆的石子移至偶数堆，则相当于是在奇数堆中清除了这些石子。

2. 若对手将偶数堆的石子移至奇数堆，则可以将这些石子从奇数堆再移回偶数堆，相当于“抵消”了这次对手的行动。

Q：为啥阶梯 nim 的结果不是与只看偶数堆的普通 nim 一样？证明起来好像只用把奇偶调换一下就可以了啊？

A：关键就在于那个“抵消”操作。若对手将第二堆中的石子挪到第一堆，就无法再将那些石子移回偶数堆了。

三：本题思路

看到这一题的特殊要求“每堆石子个数都不少于前一堆的石子个数”时，首先考虑差分。因为这个条件可以使差分中的每一项均为正。

设 $c_i = a_i - a_{i - 1}$，其中第一项 $c_1 = a_1$。

好像没什么感觉。我们拿走一些石子试试。

从第 $i$ 堆中取走 $x$ 颗石子，则 $c_i$ 变为 $c_i - x$，$c_{i + 1}$ 变为 $c_{i + 1} + x$。

和阶梯 nim 神似有木有？只不过变成从前往后拿，所以需要倒着取奇数堆。

那么……

四：代码奉上

因为上面写的很详细就不加注释了

#include <iostream>
using namespace std;

int c[1001];

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;

		int la = 0;
		for (int i = 1; i <= n; i++)
		{
			int z;
			cin >> z;
			c[i] = z - la;
			la = z;
		}

		int nim_sum = 0;
		for (int i = n; i > 0; i -= 2)
		{
			nim_sum ^= c[i];
		}
		nim_sum ^= 0;

		if (nim_sum == 0)
		{
			cout << "NIE" << endl;
		}
		else
		{
			cout << "TAK" << endl;
		}
	}
}

https://blog.csdn.net/tenkuo/article/details/153619215

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int u;
int n;
int a[10004];
int c[10004];
int main()
{
    scanf("%d",&u);
    while(u--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
            c[i]=a[i]-a[i-1];
        int ans=0;
        for(int i=n;i>=1;i-=2)
            ans^=c[i];
        if(ans)printf("TAK\n");
        else printf("NIE\n");
    }
    return 0;
}