【題目大意】
猴子和Kruskal玩一個(gè)取石子游戲，給定n堆石子，n不大于200，每堆石子的個(gè)數(shù)大于2小于2 ^
32，雙方輪流取子，每次可以從一堆中取最多k個(gè)，當(dāng)一方取完石子后某堆石子的個(gè)數(shù)是素?cái)?shù)的話那么當(dāng)前玩家獲勝。問(wèn)猴子是否有必勝策略。
【題目分析】
這是一道BT題，中間設(shè)置了許多trick。開(kāi)始對(duì)題意沒(méi)有完全理解，錯(cuò)了很多次，后來(lái)找來(lái)了數(shù)據(jù)，才發(fā)現(xiàn)了問(wèn)題。
題目中描述的獲勝策略是："A
player wins if after his move the size of some heap is a prime
number."這句話乍一看以為是取完石子后剩下的石子個(gè)數(shù)是素?cái)?shù)的時(shí)候就獲勝，其實(shí)還隱藏著另一種可能：如果多堆石子個(gè)數(shù)是素?cái)?shù)，當(dāng)前玩家無(wú)論怎樣取都能獲勝，因?yàn)樵谒⊥曛螅渌训氖觽€(gè)數(shù)是素?cái)?shù)，也滿足獲勝條件。
接下來(lái)考慮一般情況。這個(gè)題目是限制中間狀態(tài)的Nim游戲，也就是說(shuō)，對(duì)于一堆個(gè)數(shù)為n的石子而言，它的SG值取決于小于n的最大素?cái)?shù)。注意這里題設(shè)又有了一個(gè)小trick，題目說(shuō)明了需要取1到k個(gè)，如果當(dāng)前石子個(gè)數(shù)本身是素?cái)?shù)，當(dāng)然是沒(méi)用的，因此是小于n的最大素?cái)?shù)。設(shè)小于n的最大素?cái)?shù)是p(題目中說(shuō)明了石子個(gè)數(shù)大于2，因此p一定存在)，那么可以在k步以?xún)?nèi)到達(dá)p的一定是必勝態(tài)，而且是直接獲勝，需要在輸入的時(shí)候特判(這一點(diǎn)需要注意，在解決限制中間狀態(tài)的Nim游戲時(shí)一般都需要特判)。然后就是p
+ k + 1這個(gè)狀態(tài)，因?yàn)樗蛇_(dá)的狀態(tài)全是必勝態(tài)，因此它是必?cái)B(tài)，SG值為0。現(xiàn)在考慮大于p + k + 1的狀態(tài)，問(wèn)題出來(lái)了。以p + k +
2這個(gè)狀態(tài)為例，因?yàn)樗梢缘竭_(dá)p + 2 ... p + k + 1這些狀態(tài)，因?yàn)閜 + 2 ... p +
k都是直接獲勝狀態(tài)，如何判定他們的SG值呢？如果假設(shè)它們的SG值是1，那么p + k +
2這個(gè)狀態(tài)的SG值應(yīng)該是2。但是思考一下SG值的定義，它是定義在一個(gè)DAG上的，所有的狀態(tài)最后都是可以在有限步內(nèi)轉(zhuǎn)移到終止態(tài)(必?cái)B(tài))。但是p + 1 ...
p + k這些狀態(tài)都轉(zhuǎn)移到了p這個(gè)狀態(tài)上，我們肯定不能認(rèn)定p狀態(tài)是終止態(tài)，因此僅僅憑借p + 1 ... p +
k這些狀態(tài)是必勝態(tài)就簡(jiǎn)單的把它們的SG值設(shè)為1是不恰當(dāng)?shù)模贿@些限制狀態(tài)和以前的題目還不同，這些限制狀態(tài)都不能轉(zhuǎn)移到終止態(tài)上，但是由于題目的要求，它們又都是必勝態(tài)，因此把它們的SG值設(shè)為無(wú)窮大更合適些。
仔細(xì)思考一下帶限制狀態(tài)的SG游戲，可以發(fā)現(xiàn)，它們和一般的SG游戲的區(qū)別在于，在分析一般的SG游戲的時(shí)候，對(duì)于一個(gè)狀態(tài)圖而言，轉(zhuǎn)移到終止態(tài)的時(shí)候并不意味著游戲結(jié)束，因?yàn)橥婕铱梢酝ㄟ^(guò)走其他的狀態(tài)圖來(lái)保證是否達(dá)到必勝態(tài)；但是帶限制狀態(tài)的SG游戲，限制的狀態(tài)雙方都是不敢走的，因?yàn)橐坏┮环阶呷胂拗茽顟B(tài)，另一方立刻獲勝，游戲就終止了。可以認(rèn)為，只要走入限制態(tài)就相當(dāng)于認(rèn)輸，對(duì)于雙方玩家而言肯定都不會(huì)這樣做，因此這些限制狀態(tài)就成了“死狀態(tài)”，完全可以忽視這些狀態(tài)（也就是說(shuō)不存在到這些狀態(tài)的轉(zhuǎn)移）。通過(guò)上述分析，我們可以認(rèn)定p
+ k +
2這個(gè)狀態(tài)的SG值應(yīng)該是1而不是2。
現(xiàn)在這個(gè)問(wèn)題的做法就比較明朗了，對(duì)于每堆石子，去掉限制態(tài)的討論后，就變成了在集合{1...k}中選擇元素的一個(gè)Subtraction
Game，它的SG值是模(k +
1)循環(huán)的。
然后就是求最近素?cái)?shù)的問(wèn)題了，這個(gè)沒(méi)有好辦法，只能暴力枚舉。對(duì)于一個(gè)數(shù)n，在sqrt(n)到n之間存在素?cái)?shù)（感覺(jué)應(yīng)該是，但是不會(huì)證），因此最多枚舉sqrt(n)次就能找到解。但是每次枚舉判素的復(fù)雜度還是sqrt(n)，總復(fù)雜度還是比較高，我在本地跑數(shù)據(jù)跑了3秒，交上去超時(shí)了（SPOJ的時(shí)限10秒，這居然也超時(shí)，數(shù)據(jù)夠變態(tài)）。想了很久也沒(méi)有什么新的算法，無(wú)奈只能在判素上下點(diǎn)功夫，直接把Miller-Rabin搞出來(lái)了，速度提高到了2秒，仍然超時(shí)。后來(lái)又加了一些常數(shù)上的優(yōu)化，終于過(guò)了。
【總結(jié)】
這個(gè)題目做了很長(zhǎng)時(shí)間，一方面是審題不清，錯(cuò)了幾次；另一方面是對(duì)于SG的理論理解的不夠透徹，想了很久終于想明白了；再有就是優(yōu)化算法也花了很長(zhǎng)時(shí)間。不過(guò)通過(guò)這個(gè)題目對(duì)于SG理論的理解又進(jìn)了一步，感覺(jué)不錯(cuò)，呵呵。
注：本文作于2009年8月6日 9點(diǎn)27分