【題目大意】
　　猴子和Kruskal玩一個取石子游戲，給定n堆石子，n不大于200，每堆石子的個數大于2小于2 ^ 32，雙方輪流取子，每次可以從一堆中取最多k個，當一方取完石子后某堆石子的個數是素數的話那么當前玩家獲勝。問猴子是否有必勝策略。

【題目分析】
　　這是一道BT題，中間設置了許多trick。開始對題意沒有完全理解，錯了很多次，后來找來了數據，才發現了問題。
　　題目中描述的獲勝策略是："A player wins if after his move the size of some heap is a prime number."這句話乍一看以為是取完石子后剩下的石子個數是素數的時候就獲勝，其實還隱藏著另一種可能：如果多堆石子個數是素數，當前玩家無論怎樣取都能獲勝，因為在他取完之后，其他堆的石子個數是素數，也滿足獲勝條件。
　　接下來考慮一般情況。這個題目是限制中間狀態的Nim游戲，也就是說，對于一堆個數為n的石子而言，它的SG值取決于小于n的最大素數。注意這里題設又有了一個小trick，題目說明了需要取1到k個，如果當前石子個數本身是素數，當然是沒用的，因此是小于n的最大素數。設小于n的最大素數是p(題目中說明了石子個數大于2，因此p一定存在)，那么可以在k步以內到達p的一定是必勝態，而且是直接獲勝，需要在輸入的時候特判(這一點需要注意，在解決限制中間狀態的Nim游戲時一般都需要特判)。然后就是p + k + 1這個狀態，因為它可達的狀態全是必勝態，因此它是必敗態，SG值為0。現在考慮大于p + k + 1的狀態，問題出來了。以p + k + 2這個狀態為例，因為它可以到達p + 2 ... p + k + 1這些狀態，因為p + 2 ... p + k都是直接獲勝狀態，如何判定他們的SG值呢？如果假設它們的SG值是1，那么p + k + 2這個狀態的SG值應該是2。但是思考一下SG值的定義，它是定義在一個DAG上的，所有的狀態最后都是可以在有限步內轉移到終止態(必敗態)。但是p + 1 ... p + k這些狀態都轉移到了p這個狀態上，我們肯定不能認定p狀態是終止態，因此僅僅憑借p + 1 ... p + k這些狀態是必勝態就簡單的把它們的SG值設為1是不恰當的；這些限制狀態和以前的題目還不同，這些限制狀態都不能轉移到終止態上，但是由于題目的要求，它們又都是必勝態，因此把它們的SG值設為無窮大更合適些。
　　仔細思考一下帶限制狀態的SG游戲，可以發現，它們和一般的SG游戲的區別在于，在分析一般的SG游戲的時候，對于一個狀態圖而言，轉移到終止態的時候并不意味著游戲結束，因為玩家可以通過走其他的狀態圖來保證是否達到必勝態；但是帶限制狀態的SG游戲，限制的狀態雙方都是不敢走的，因為一旦一方走入限制狀態，另一方立刻獲勝，游戲就終止了。可以認為，只要走入限制態就相當于認輸，對于雙方玩家而言肯定都不會這樣做，因此這些限制狀態就成了“死狀態”，完全可以忽視這些狀態（也就是說不存在到這些狀態的轉移）。通過上述分析，我們可以認定p + k + 2這個狀態的SG值應該是1而不是2。
　　現在這個問題的做法就比較明朗了，對于每堆石子，去掉限制態的討論后，就變成了在集合{1...k}中選擇元素的一個Subtraction Game，它的SG值是模(k + 1)循環的。
　　然后就是求最近素數的問題了，這個沒有好辦法，只能暴力枚舉。對于一個數n，在sqrt(n)到n之間存在素數（感覺應該是，但是不會證），因此最多枚舉sqrt(n)次就能找到解。但是每次枚舉判素的復雜度還是sqrt(n)，總復雜度還是比較高，我在本地跑數據跑了3秒，交上去超時了（SPOJ的時限10秒，這居然也超時，數據夠變態）。想了很久也沒有什么新的算法，無奈只能在判素上下點功夫，直接把Miller-Rabin搞出來了，速度提高到了2秒，仍然超時。后來又加了一些常數上的優化，終于過了。

【總結】
　　這個題目做了很長時間，一方面是審題不清，錯了幾次；另一方面是對于SG的理論理解的不夠透徹，想了很久終于想明白了；再有就是優化算法也花了很長時間。不過通過這個題目對于SG理論的理解又進了一步，感覺不錯，呵呵。

注：本文作于2009年8月6日 9點27分

【概述】
　　最近的幾次比賽，博弈的題目一直不少，而且博弈問題是一塊比較復雜、龐大的內容，因此在這里小結一下，希望能夠幫自己理清一些思路，爭取也多來幾個系列，呵呵。

競賽中出現的組合游戲問題一般都滿足以下特征：
　　　　1. 二人博弈游戲，每個人都采用對自己最有利的策略，并且是兩個人輪流做出決策
　　　　2. 在游戲中的任意時刻，每個玩家可選擇的狀態是固定的，沒有隨機成分
　　　　3. 游戲在有限步數內結束，沒有平局出現
　　大部分的題目都滿足上述條件，因此這里只討論在上述條件范疇內的博弈問題。這類博弈問題，通常還有若干分類。一種是規定移動最后一步的游戲者獲勝，這種規則叫做Normal Play Rule；另一種是規定移動最后一步的游戲者輸，這種規則叫做Misere Play Rule，也稱為Anti-SG游戲。此外，對于游戲的雙方，如果二者博弈的規則相同，那么稱為這類游戲是對等(impartial games)的；否則稱為不平等游戲(partizan games )。當初WHU的那場比賽就是由于對于這個概念不是很清晰，導致看完題目之后就用SG定理來做，浪費了很多機時。實際上，解決不平等博弈問題的方法和普通的博弈問題（SG游戲）是有區別的，一般會采用動態規劃或者surreal number。

【博弈基礎知識】
　　在SG游戲中，最為人熟知的是必勝必敗態，也叫NP態理論。注意的是，P態對應的是先手必敗態，N態對應的是先手必勝態。必勝必敗態理論是：
　　1. All terminal positions are P-positions
　　2. From every N-position, there is at least one move to a P-position
　　3. From every P-position, every move is to an N-position
　　英文的表述非常簡潔清晰，而且這個理論也很好理解，如果在當前狀態的下一步可以走到必敗態，那么當前玩家就可以走到那個狀態，把必敗態推給另一方；如果所有可達狀態都是必勝態，那么當前玩家無論如何走，都會把必勝態讓給對方。根據必勝必敗態理論，我們可以遞歸的求出每個狀態是N態還是P態。必勝必敗態理論其實已經把博弈問題轉化成了一個有向圖，借助圖這個模型來分析問題，使得問題變得形象了許多。需要注意的是，這種SG游戲對應的有向圖是無環的，因為如果有環，那么游戲雙方就可能在環上不停的轉換狀態，游戲不能在有限步終止，這樣就不滿足組合游戲的特征3了。
　　然而在很多時候僅僅知道某個狀態是必勝還是必敗是不夠的，因為如果存在多個組合游戲（比如經典的Nim），對應的狀態集合非常大，無法直接利用必勝必敗態理論求解，因此需要用到博弈論中一個很重要的工具：SG函數。
　　某個狀態的SG函數值定義為當前狀態所有不可達的狀態編號中最小的編號，其中終止態的SG函數值是0。有了這個工具，就引入一個非常強大的定理——SG分解定理：

　　多個組合游戲的SG函數值是每個組合游戲的函數值的和。（這里的和定義為異或操作）
　　
　　SG分解定理的證明不是很難，其實和Nim的證明很像。根據這個定理，我們就知道為什么Nim的解法是異或所有的石子個數了，因為每堆石子的SG值就是石子的個數。SG分解定理告訴我們任何SG游戲都可以轉化成Nim游戲來做。
　　Nim中的一個變形就是拿走最后一塊石子的人算輸。通過修改SG的計算規則，可以得出相同的結論（因為當石子個數是1的時候SG值為0，因此要單獨處理）；當然也可以利用一個叫做SJ定理的方法來做，依然是要處理當所有堆的SG值不大于1的情況。

【博弈基本模型】
　　除了Nim模型，很多模型都看似復雜，最后都劃歸到了Nim模型上，然后利用SG分解來做的。在證明兩種模型等價的時候，可以通過計算SG值判斷是否相同，或者通過判斷必勝策略的走法將其轉化為Nim。許多模型非常的神奇，其獲勝策略又千差萬別，因此無法一一列舉，但是掌握一些經典模型是必須的，這樣通過模型的轉化可以簡化問題的難度。
　　經典模型1：Nim變種。包括：
　　　　(1) 樓梯Nim。把奇數臺階的石子作為Nim，二者等價，因為必勝的策略是相同的。
　　　　(2) 每次可以取k堆，這個是經典的Moore Nim。它是泛化的Nim游戲。
　　　　(3) 兩堆石子，每次可以取一堆或兩堆，從兩堆取得時候個數必須相同，誰先取完獲勝。這個是著名的威佐夫博弈，跟黃金分割數有關，具體證明不是很清楚，但是用SG值打表可以找出規律。代碼如下：

　　　　(4) Subtraction Games。一種通用的Nim游戲，每次從可用狀態集合中選擇下一步的狀態，有很多變形，核心思想還是計算SG函數值。
　　　　(5) Take-and-Break Game。每次把局面分成多個Nim子游戲，利用SG分解定理求出對應的SG值。
　　經典模型2：翻硬幣游戲(Coin Turning Game)
　　　　(1) 一維的翻硬幣游戲，每次可以翻1個或兩個。通過單獨考慮每個可以翻的硬幣發現，Coin Turning Game的SG值和Nim等價，因此兩個模型等價。需要注意的是，許多翻硬幣游戲根據題目的要求，一般編號從0開始。
　　　　(2) 一維的翻硬幣游戲，每次可以翻1個或兩個，限定了翻第二枚硬幣的范圍，那么就和Subtraction Game等價了。
　　　　(3) 一維的翻硬幣游戲，每次可以翻1個、2個或3個，這個游戲叫做Mock Turtles，有一個神奇的規律，是Odious Number序列。
　　　　(4) 高維的翻硬幣游戲，需要用到Nim積和Tartan定理。
　　翻硬幣模型的變化更多，很多模型都有一些奇妙的規律，需要打表才能發現。
　　經典模型3：刪邊游戲(Green Hackenbush)
　　　　(1) 樹的刪邊游戲：Colon原理證明這種模型和Nim依然是等價的，多個叉的SG值異或就是對應根節點的SG值。
　　　　(2) 無向圖刪邊游戲：利用Fursion定理收縮圈，然后就轉換成樹的刪邊游戲了，不過這個定理還不會證。

注：本文作于2009年8月3日 09點33分

　　我發現原來那個百度空間的文章基本都是扯閑淡的，不過這樣也好，以后那個博客專門用來扯淡，這個應該多寫一些技術文章。
　　以前有許多技術文章寫在了我們隊的那個博客，現在那個基本荒廢了，我打算把以前那里寫過的還比較有紀念意義的文章再弄過來，要不然真就被我遺忘了。
　　不過那個博客都是隱藏文章，rss導不過來，只好一篇篇復制了，囧。

　　P.S.在那個博客寫的文章真規范，跟范文似的，哈哈。
我也當回標題黨。

看到SJTU在中國本土奪冠，心里由衷的感到高興。按說作為一個旁觀者我完全沒有理由心里如此舒坦，可能是因為SJTU超過了THU讓我感到一絲幸災樂禍，這只能解釋成心里變態因為THU從來沒有得罪過我，況且THU還有個可愛的MM我應該憐香惜玉才對。可能另一個可能的解釋是看慣了THU在各大區域賽包攬冠軍突然希望另一股勢力來證明THU不是在大陸獨大的，這個final的結果恰好滿足了我陰暗的心里。

當然比賽這個東西本身有極強的不確定性，一次的成績代表不了什么，但是誰讓這是final呢。也許我應該說高考考得爛不代表學習不好，可惜誰讓這是高考呢。幸好競賽比高考強就強在我們在競賽中能have fun。

今年中國在final取得的成績比去年好很多，有冠軍不說，牌也拿得多了（當然也包括我們寶島臺灣的大學）。HIT也總算在final上邁出了第一步，luzilon他們已經盡力了，我相信以后的final中HIT會邁出第二步、第三步。

HEU作為主辦方，真的非常用心的在辦比賽，當我得知現場直播中那個同美女主持一起負責主持的大叔居然是HEU的教務處副主任的時候，我真TMD的震撼了。那可是教務處的副主任啊，居然對acm這么了解！他甚至都知道icpc的那個標志的含義。要是HIT教務處的副主任也能這么了解該多好啊，哪怕隨便教務處的哪個老師了解也行，不過據我所知，好像沒幾個老師真正了解，他們只知道數模拿獎比acm多，而且那幫娘們們更青睞于嗑瓜子、斗地主、時而不時的刁難學生并以此為樂。

本來看final的過程挺開心的，可有時候又情不自禁的為一些無聊的話生閑氣。就比如HEU的直播有廣告，那太正常了啊，誰不指望在這個時候宣傳一下自己的學校啊，花了這么多錢辦個比賽當然是要有回報的。可PKU的bbs里就有些人不滿了，要么說人家主持人不行，要么嫌人家廣告多，不放點厥詞就不知干啥好了。當然我也為看lrj老師的訪談時突然變成介紹HEU學校概況而感到不爽，但是一想人家也不容易，也就忍了。<孔子>的導演胡玫說的好：讓中國人說一句好，真的很難；讓中國人罵一點，簡直就“嘩嘩嘩”地來。我也是屬于"嘩嘩嘩"來那伙的，經常挑三揀四，不過有時良心發現一想別人也不容易，因此大多數情況下也很尊重這些用心為我們提供物質或文化上服務的人。

聽余勇老師和lrj老師訪談的時候，他們談到的一點我很贊同。icpc競賽其實考得不僅僅是編程、算法和數學，更多的是知識面和臨場發揮、隨即應變的能力（Da Lord也不止一次說過這一點）。其實后者作為一個人的軟實力在以后的工作和學習中非常重要，我在第二年的icpc生涯中也比較在意自己這方面的能力，無奈先天條件比較差，最終賽場上還是沒能做到“我自閑庭信步”的那種靈感乍現的狀態，不過這個經歷卻是一筆寶貴的人文財富。

明天就是小年了，大年也不遠了，參加完比賽的童鞋們應該都爭先恐后的踏上了熙熙攘攘的春運火車，也許他們正為漫長的旅途而發愁，可此時的我卻真的有些羨慕他們呢。
　　正月眼看著就要過去了，一個月的沉寂足以證明我是多么的懶惰，在這大地回暖的日子里，我懷著誠惶誠恐的生怕被將來的自己忘記的心情在這個博客上寫下倉促的一筆。
　　offer好像出了點問題，遲遲沒有收到，這點很是讓我擔心。有時禁不住去想，如果最后真的是一場空，我將何去何從？生活的不確定性帶來的驚喜和悲痛有時似乎真的不如翹首企盼的過程帶給人的焦慮更讓人刻骨銘心，誠然，若干個月后的事實會證明今時今日我在這里純粹是杞人憂天或者是暴風雨前的哀鳴，但今時今日的我卻按捺不住為若干個月后的事實而抓耳撓腮，人就是個愛YY的動物。
　　很想為匆匆滑過的一個月寫點什么，抬起的手指卻遲遲敲不下去，荒廢的歲月太多以至于忘記了時間的存在。掃清了12月的遺留計劃，啃掉了CSAPP，對OS相關的知識有了些許頓悟；然后每天興致勃勃的打算為畢設做點什么最后卻捧起遙控器或者易中天看了起來。看完55元的Avatar后大呼劇情狗血最后卻不得不為在中國乃至全世界的無敵票房為卡梅隆大豎手指；然后驚訝的發現<欺詐游戲>里面的戶田惠梨香繼續扮演著她在<死亡筆記>里的傻姑角色不禁懷疑起這么漂亮的小姑娘在現實生活中的智商來。我不得不承認時間在專注的時候過得很快，在虛度的時候過得也很快，我突然發覺我的記憶中只有高中的時間過得最慢，然后發覺原來高中的時間既沒有專注也不是虛度，而是煎熬。
　　躺在床上時而會回想起高中和大學時期做的一些事情，某些決策如果當初不那樣做會怎樣，然后就會想出很多種可能，不知不覺眼角竟淌出淚來，為那段青蔥的歲月而流，畢竟，人生的彎路，只有走過了，才會有體會。