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

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

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

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

nn 可能很大,但序列中 11 的个数不超过 2×1052\times 10^5

01 序列的输入方式是 mm递增的正整数,描述这些 1 的下标,下标从 11 开始。

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

妙妙题。

不难发现,操作相当于移动 11。不妨设 bi=naib_i=n-a_i,游戏即转化为所有 bib_i 均为 00 时无法操作。

  1. ai=1a_i=1 的情况:

    1. aj=0a_j=0,相当于让 bibi(ji)b_i\to b_i-(j-i)
    2. aj=1a_j=1,相当于让 bi0b_i\to 0bj0b_j\to 0
  2. ai=0a_i=0 的情况:

    1. aj=0a_j=0,相当于新建两个 bm+1=nib_{m+1}=n-ibm+2=njb_{m+2}=n-j
    2. aj=1a_j=1,相当于让 bjbj+(ji)b_j\to b_j+(j-i)

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

设当前异或和为 xx,则:

  • 1.1 相当于 Nim 游戏的正常操作;
  • 1.2 相当于让 bibi(ji)b_i\to b_i-(j-i),由于存在 bj=bi(ji)b_j=b_i-(j-i),所以这两个在异或和中抵消了,相当于都变成了 00

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

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

  • 2.1 中 nin-i 一定不等于 njn-j,贡献一定不为 00
  • 2.2 中 贡献还是一定不为 00

所以 ai=0a_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;
}