【题目大意】
　　猴子和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后大呼剧情狗血最后却不得不为在中国乃至全世界的无敌票房为卡梅隆大竖手指；然后惊讶的发现<欺诈游戏>里面的户田惠梨香继续扮演着她在<死亡笔记>里的傻姑角色不禁怀疑起这么漂亮的小姑娘在现实生活中的智商来。我不得不承认时间在专注的时候过得很快，在虚度的时候过得也很快，我突然发觉我的记忆中只有高中的时间过得最慢，然后发觉原来高中的时间既没有专注也不是虚度，而是煎熬。
　　躺在床上时而会回想起高中和大学时期做的一些事情，某些决策如果当初不那样做会怎样，然后就会想出很多种可能，不知不觉眼角竟淌出泪来，为那段青葱的岁月而流，毕竟，人生的弯路，只有走过了，才会有体会。