题解 : SP20951

· · 题解

观察到：当所有堆中石子个数相同时，若有偶数堆，则：

  1. 先手执行第一步，此时设取走第一堆 x_1 个。
  2. 后手取走第二堆 x_1 个。
  3. 先手第三步，当合法时，取走第一或三堆 x_2 个。
  4. 后手取走第（先手取的堆的编号 +1）个堆的 x_2 个。
  5. 重复以上操作，最后先手失败。

若有奇数堆，则先手可取完第一堆得到偶数堆的情形，然后得到先手必胜。

为了方便，先做一步转化：对原石子序列进行差分，则一次操作相当于将第 i 堆中 s 个石子（stone_i \le s）扔进第 i+1 堆中。若 i = n，则将石子扔出游戏。

在转化后，上述观察相当于：第一堆有 n 个石子，其他堆都没有的情况。若偶数堆，则在先、后操作各一次后，只有从右数偶数堆内是有石子的。

若将观察得到的方法推广至一般的游戏中，可以发现若先手移动从右数偶数堆时，后手总可以移动下一堆，“抵消先手操作带来的影响”。这是因为这样过程之后移动的石子要么被移出游戏要么还在右数偶数堆中。以此为前提，游戏转化为右数奇数堆构成的 Nim 游戏。并且回过来想，不管在右边奇数堆构成的 Nim 游戏先手必胜或必败，移动偶数堆一定不会导致结果更优。所以方法正确性成立。

#include <bits/stdc++.h>
using namespace std;

int TAT;

int n;
int a[1002], b[1002];

int main(){

    scanf("%d",&TAT);

    while(TAT--){

        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]), b[i] = a[i] - a[i-1];

        int Ans = 0;
        for(int i=n;i>=1;i-=2){
            Ans ^= b[i];
        }

        if(Ans == 0) printf("NIE\n");
        else printf("TAK\n");

    }

    return 0;
}