首页 > 代码库 > 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解题报告