首页 > 代码库 > HDU3032_NimOrNotNim解题报告
HDU3032_NimOrNotNim解题报告
HDU3032 Nim or not Nim 解题报告:思路与证明
胡明晓
Description
Alice and Bob is tired of playing Nim under the standard rule, so they make a difference by also allowing the player to separate one of the heaps into two smaller ones. That is, each turn the player may either remove any number of objects from a heap or separate a heap into two smaller ones, and the one who takes the last object wins.
Input
Input contains multiple test cases. The first line is an integer 1≤T≤100, the number of test cases. Each case begins with an integer N, indicating the number of the heaps, the next line contains N integers s00, s11, ...., sN?1N?1, representing heaps with s00, s11, ..., sN?1N?1 objects respectively.(1≤N≤106, 1≤Sii≤231-1)
Output
For each test case, output a line which contains either "Alice" or "Bob", which is the winner of this game. Alice will play first. You may asume they never make mistakes.
解题思路
Nim游戏的SG函数计算如下:
g(x) = mex{g(y) | y是x的后继状态},其中mex S表示S中未出现的最小非负整数。
g(x0)=0。(x0为终止状态)
设状态用石子数向量(a1,…,am)表示,特别地,单堆的状态表示成a。
将一堆石子分成两堆,等于将一个一堆的Nim游戏A变成两个一堆游戏的和B,这两个一堆游戏之和也是A的后继状态。计算A的SG函数时,除了考虑普通后继状态之外,还要将B的SG值加入mex计算,而B的SG值是两个成员游戏SG值的异或◎(根据和游戏定理)。
下面计算单堆状态的SG函数。
g(0)=0,
g(1)=mex{g(0)}=1,
g(2)=mex{g(0), g(1), g(1,1)}=mex{ g(0), g(1), g(1)◎g(1))=2,
g(3))=mex{g(0), g(1), g(2), g(1)◎g(2))=mex{0,1,2,3}=4,
g(4)=mex{g(0), g(1), g(2), g(3), g(1)◎g(3)), g(2)◎g(2))=mex{0,1,2,4,5,0}=3,
g(5)=mex{g(0), g(1), g(2), g(3), g(4), g(1)◎g(4), g(2)◎g(3))
=mex{0,1,2,4,3, 1◎3, 2◎4}=5,
g(6)=mex{0,1,2,4,3, 5, 1◎5, 2◎3, 4◎4}=6,
g(7)=mex{0,1,2,4,3, 5, 6, 1◎6, 2◎5, 4◎3}=8,
g(8)=mex{0,1,2,4,3, 5, 6, 8,1◎8, 2◎6, 4◎5, 3◎3}=7,
g(9)=mex{0,1,2,4,3,5,6,8,7, 1◎7, 2◎8, 4◎6, 3◎5}=9,
……
发现规律是g(a)=a,但g(4k+3)与g(4k+4)的值对调一下。即
g(a)=a (a=4k+1或4k+2)
g(a)=4k+4 (a=4k+3) (*)
g(a)=4k+3 (a=4k+4)
严格的证明如下。
证明:设a=4k+r(r=1,2,3,4),k=0,1,……,即按k分成4个一组,对组号k进行数学归纳。
为叙述方便,将后继状态的SG值集合划分成两类:S1和S2,分别表示单状态和分解状态的值,即S1={g(0),g(1),…g(a-1)},S2={g(a1)◎g(a2) | a1+a2=a,a1>0,a2>0}。g(a)=mex S=mex(S1∪S2)。
当k=0时,显然成立。
假设当k<=m时(*)式成立,于是可以列出非零状态a和g(a)的二进制末两位后缀对应情况,如下表:
表1
a |
00 |
01 |
10 |
11 |
g(a) |
11 |
01 |
10 |
00 |
进一步,a1、a2和g(a1)◎g(a2)的二进制末两位后缀对应情况如下表:
表2
a2 g(a1)◎g(a2) a1 |
00 |
01 |
10 |
11 |
00 |
11◎11=00 |
11◎01=10 |
11◎10=01 |
11◎00=11 |
01 |
01◎11=10 |
01◎01=00 |
01◎10=11 |
01◎00=01 |
10 |
10◎11=01 |
10◎01=11 |
10◎10=00 |
10◎00=10 |
11 |
00◎11=11 |
00◎01=01 |
00◎10=10 |
00◎00=00 |
当k=m+1时,对k组的4个状态a分别证明。
(1)a=4k+1
a的后缀是01,由归纳假设,S1中0,1,…,a-1各出现一次,而S2中只有10后缀的值,没有01后缀的值(见表2阴影格子),所以g(a)=a。符合(*)式结果。
(2)a=4k+2
a的后缀是10,由归纳假设及情形(1),S1中0,1,…,a-1各出现一次,而S2中有00、01后缀的值,没有10后缀的值(见表2),所以g(a)=a。符合(*)式结果。
(3)a=4k+3
a的后缀是11,由归纳假设及情形(1)(2),S1中0,1,…,a-1各出现一次,而S2中全是11后缀的值(见表2),而且能取到a值本身(作分解a=1+(a-1)即能),所以g(a)=a+1=4k+4。符合(*)式结果。
(4)a=4k+4
a的后缀是00,由归纳假设及情形(1)(2)(3),S1中0,1,…,a-2,a各出现一次,a-1没出现,而S2中有00、01后缀的值,没有11后缀的值(见表2),也不可能出现a-1,所以g(a)=a-1=4k+3。符合(*)式结果。
总之,k=m+1时,(*)式也成立。证毕。
参考代码:
(待加)
HDU3032_NimOrNotNim解题报告