【jzoj 4024】 【佛山市選2015】石子游戲 {篩素數 博弈論(NIM博弈/SG函式)}

NO IMAGE

題目

Description
Alice 和 Bob 總喜歡聚在一起玩遊戲(T_T),今天他(她)們玩的是一款新型的取石子游戲。遊戲一開始有N堆石子,Alice 和 Bob 輪流取出石子。在每次操作中,遊戲者必須選擇其中的一堆石子,並作出下列的其中一種操作:
(1)移去整堆石子
(2)假設石子堆中有X顆石子,取出Y顆石子,其中1<=Y 【假的,是取與x 互質(小於等於x)的數】
遊戲結束的條件是:取出最後一顆石子的人勝出。眾所周知,Alice和Bob都是絕頂聰明的,假設他們在遊戲中都採取最優的策略,問最後誰會勝出遊戲呢?

Alice先取。

Input
第一行包含一個整數T,表示測試資料的組數。
接下來T組測試資料,在每組資料中,第一行包含一個整數N,表示有多少堆石子。第二行N個正整數,分別表示每堆有多少顆石子。

Output
每組測試資料輸出一行,表示獲勝者的名字(Alice 或者 Bob)。


解題思路

通常的Nim遊戲的定義是這樣的:有若干堆石子,每堆石子的數量都是有限的,合法的移動是”選擇一堆石子並拿走若干顆(不能不拿)”,如果輪到某個人時所有的石子堆都已經被拿空了,則判負(因為他此刻沒有任何合法的移動)。

任何一個ICG都可以通過把每個局面看成一個頂點,對每個局面和它的子局面連一條有向邊來抽象成這個”有向圖遊戲”。下 面我們就在有向無環圖的頂點上定義Sprague-Grundy函式。首先定義mex(minimal excludant)運算,這是施加於一個集合的運算,表示最小的不屬於這個集合的非負整數。例如mex{0,1,2,4}=3、mex{1,3,5}=0、mex{}=0。對於一個給定的有向無環圖,定義關於圖的每個頂點的Sprague-Grundy函式g如下:g(x)=mex{ g(y) | y是x的後繼 }。

sg[i]表示取走i個的sg值,因為本題要求必須要是質數,所以取的i是最小質因數。


程式碼

#include<cstdio>
using namespace std; 
int t,n,g,sg[1000001],num;
int main()
{
scanf("%d",&t);
sg[1]=1; num=1;
for (int i=2;i<=1000000;i  )
{
if (!sg[i])
{
sg[i]=  num; 
for (int j=i;j<=1000000;j =i)
if (!sg[j]) sg[j]=num; 
}
}  
while (t--)
{
int b=0; 
scanf("%d",&n); 
for (int i=1;i<=n;i  )
scanf("%d",&g),b^=sg[g];
if (b!=0) printf("Alice\n"); else printf("Bob\n"); 
}
}