P9003 [RC-07] Game Theory 做题记录

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

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

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

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

01 序列的输入方式是 $m$ 个递增的正整数，描述这些 1 的下标，下标从 $1$ 开始。

$1\le n\le 10^{18}$，$2 \le m\le 10^6$。保证 $m$ 是偶数，保证为 1 的下标是递增顺序给出的。

妙妙题。

不难发现，操作相当于移动 $1$。不妨设 $b_i=n-a_i$，游戏即转化为所有 $b_i$ 均为 $0$ 时无法操作。

1. $a_i=1$ 的情况：

   1. $a_j=0$，相当于让 $b_i\to b_i-(j-i)$；
   2. $a_j=1$，相当于让 $b_i\to 0$，$b_j\to 0$；

2. $a_i=0$ 的情况：

   1. $a_j=0$，相当于新建两个 $b_{m+1}=n-i$ 和 $b_{m+2}=n-j$；
   2. $a_j=1$，相当于让 $b_j\to b_j+(j-i)$；

下面将证明这个游戏等价于 Nim 游戏，即先手必胜当且仅当 $\oplus_ib_i\not=0$。

设当前异或和为 $x$，则：

• 1.1 相当于 Nim 游戏的正常操作；
• 1.2 相当于让 $b_i\to b_i-(j-i)$，由于存在 $b_j=b_i-(j-i)$，所以这两个在异或和中抵消了，相当于都变成了 $0$；

并且不难发现 “$[1,i]$ 区间有奇数个 $1$” 这个限制是没有任何用的，因为 Nim 游戏中从 $x\not=0$ 转移到 $x=0$ 的操作方法是找到一个二进制最高位和 $x$ 的最高位相同的 $b_k$，并让它减去 $b_k-(x\oplus b_k)$。设最大的满足条件的 $k$ 为 $p$，则满足 $b_i>b_p$ 的 $i$ 一定有偶数个，那么此时操作 $b_p$ 即可。

那么注意到 $a_i=1$ 的情况已经涵盖了 Nim 游戏的所有合法操作，下面来证明 $a_i=0$ 的情况不会出现。不难发现 $a_i=0$ 的操作出现的目的一定是停在 $x=0$ 的情况，那么只需要考虑操作产生的贡献有没有可能是 $0$ 即可：

• 2.1 中 $n-i$ 一定不等于 $n-j$，贡献一定不为 $0$；
• 2.2 中 贡献还是一定不为 $0$；

所以 $a_i=0$ 的操作一定不会出现。

综上，证毕。

代码如下：

#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;
}