【題目大意】
　　猴子和Kruskal玩一個取石子游戲，給定n堆石子，n不大于200，每堆石子的個數(shù)大于2小于2 ^ 32，雙方輪流取子，每次可以從一堆中取最多k個，當(dāng)一方取完石子后某堆石子的個數(shù)是素數(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ù)是素數(shù)的時候就獲勝，其實(shí)還隱藏著另一種可能：如果多堆石子個數(shù)是素數(shù)，當(dāng)前玩家無論怎樣取都能獲勝，因?yàn)樵谒⊥曛螅渌训氖觽€數(shù)是素數(shù)，也滿足獲勝條件。
　　接下來考慮一般情況。這個題目是限制中間狀態(tài)的Nim游戲，也就是說，對于一堆個數(shù)為n的石子而言，它的SG值取決于小于n的最大素數(shù)。注意這里題設(shè)又有了一個小trick，題目說明了需要取1到k個，如果當(dāng)前石子個數(shù)本身是素數(shù)，當(dāng)然是沒用的，因此是小于n的最大素數(shù)。設(shè)小于n的最大素數(shù)是p(題目中說明了石子個數(shù)大于2，因此p一定存在)，那么可以在k步以內(nèi)到達(dá)p的一定是必勝態(tài)，而且是直接獲勝，需要在輸入的時候特判(這一點(diǎn)需要注意，在解決限制中間狀態(tài)的Nim游戲時一般都需要特判)。然后就是p + k + 1這個狀態(tài)，因?yàn)樗蛇_(dá)的狀態(tài)全是必勝態(tài)，因此它是必敗態(tài)，SG值為0。現(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)(必敗態(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游戲的時候，對于一個狀態(tài)圖而言，轉(zhuǎn)移到終止態(tài)的時候并不意味著游戲結(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)的。
　　然后就是求最近素數(shù)的問題了，這個沒有好辦法，只能暴力枚舉。對于一個數(shù)n，在sqrt(n)到n之間存在素數(shù)（感覺應(yīng)該是，但是不會證），因此最多枚舉sqrt(n)次就能找到解。但是每次枚舉判素的復(fù)雜度還是sqrt(n)，總復(fù)雜度還是比較高，我在本地跑數(shù)據(jù)跑了3秒，交上去超時了（SPOJ的時限10秒，這居然也超時，數(shù)據(jù)夠變態(tài)）。想了很久也沒有什么新的算法，無奈只能在判素上下點(diǎn)功夫，直接把Miller-Rabin搞出來了，速度提高到了2秒，仍然超時。后來又加了一些常數(shù)上的優(yōu)化，終于過了。

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

注：本文作于2009年8月6日 9點(diǎn)27分

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

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

【博弈基礎(chǔ)知識】
　　在SG游戲中，最為人熟知的是必勝必敗態(tài)，也叫NP態(tài)理論。注意的是，P態(tài)對應(yīng)的是先手必敗態(tài)，N態(tài)對應(yīng)的是先手必勝態(tài)。必勝必敗態(tài)理論是：
　　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
　　英文的表述非常簡潔清晰，而且這個理論也很好理解，如果在當(dāng)前狀態(tài)的下一步可以走到必敗態(tài)，那么當(dāng)前玩家就可以走到那個狀態(tài)，把必敗態(tài)推給另一方；如果所有可達(dá)狀態(tài)都是必勝態(tài)，那么當(dāng)前玩家無論如何走，都會把必勝態(tài)讓給對方。根據(jù)必勝必敗態(tài)理論，我們可以遞歸的求出每個狀態(tài)是N態(tài)還是P態(tài)。必勝必敗態(tài)理論其實(shí)已經(jīng)把博弈問題轉(zhuǎn)化成了一個有向圖，借助圖這個模型來分析問題，使得問題變得形象了許多。需要注意的是，這種SG游戲?qū)?yīng)的有向圖是無環(huán)的，因?yàn)槿绻协h(huán)，那么游戲雙方就可能在環(huán)上不停的轉(zhuǎn)換狀態(tài)，游戲不能在有限步終止，這樣就不滿足組合游戲的特征3了。
　　然而在很多時候僅僅知道某個狀態(tài)是必勝還是必敗是不夠的，因?yàn)槿绻嬖诙鄠€組合游戲（比如經(jīng)典的Nim），對應(yīng)的狀態(tài)集合非常大，無法直接利用必勝必敗態(tài)理論求解，因此需要用到博弈論中一個很重要的工具：SG函數(shù)。
　　某個狀態(tài)的SG函數(shù)值定義為當(dāng)前狀態(tài)所有不可達(dá)的狀態(tài)編號中最小的編號，其中終止態(tài)的SG函數(shù)值是0。有了這個工具，就引入一個非常強(qiáng)大的定理——SG分解定理：

　　多個組合游戲的SG函數(shù)值是每個組合游戲的函數(shù)值的和。（這里的和定義為異或操作）
　　
　　SG分解定理的證明不是很難，其實(shí)和Nim的證明很像。根據(jù)這個定理，我們就知道為什么Nim的解法是異或所有的石子個數(shù)了，因?yàn)槊慷咽拥腟G值就是石子的個數(shù)。SG分解定理告訴我們?nèi)魏蜸G游戲都可以轉(zhuǎn)化成Nim游戲來做。
　　Nim中的一個變形就是拿走最后一塊石子的人算輸。通過修改SG的計(jì)算規(guī)則，可以得出相同的結(jié)論（因?yàn)楫?dāng)石子個數(shù)是1的時候SG值為0，因此要單獨(dú)處理）；當(dāng)然也可以利用一個叫做SJ定理的方法來做，依然是要處理當(dāng)所有堆的SG值不大于1的情況。

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

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

注：本文作于2009年8月3日 09點(diǎn)33分

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

　　P.S.在那個博客寫的文章真規(guī)范，跟范文似的，哈哈。
我也當(dāng)回標(biāo)題黨。

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

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

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

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

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

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

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