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