The most orzed and orzing man

题目链接：http://acm.xidian.edu.cn/problem.php?id=1184

Sprague-Grundy定理：https://zhuanlan.zhihu.com/p/20611132#!

博弈论 SG函数

看到这题一脸懵逼啊，看了一下午才弄明白，是这五题最难的（但是为什么这么多人过，不科学啊）= =

Sprague-Grundy定理大致讲了这样一个东西：

对于一个满足条件的独立博弈游戏，有着必败态和必胜态，我们只需要知道当前状态是不是必胜态，就可以知道会不会赢。然而多个多个博弈游戏组成的博弈集群游戏，只知道各个游戏是否为必胜态是不行的（必胜态数大于1时，有可能胜，有可能败），因此就需要计算SG值：

对于一个必胜态，如果它只能转移到必败态，那么将其定义为一级必胜态；

如果它能转移到一级必胜态或必败态，那么将其定义为二级必胜态；

如果它能转移到一级到k级必胜态或必败态，那么将其定义为k+1级必胜态。

而多个游戏的总状态就是当前各个游戏的状态级数（必败态为零级状态）的异或值（详细证明见上面的链接）。

对于这题的单个游戏来说，当a[i]%3=0时，为必败态（零级状态），当a[i]%3=1时为一级必胜态，当a[i]%3=2时为二级必胜态，所以整个游戏群的状态为各个状态级数的异或值。

然后发现一个多星期前的cf好像有类似的博弈题是道B题当时游少直接跟我说怎么写后来也没问...惭愧= =

代码如下：

 1 #include<cstdio>
 2 using namespace std;
 3 int n,t;
 4 int main(void){
 5     while(~scanf("%d",&n)){
 6         int ans;
 7         scanf("%d",&ans);
 8         ans%=3;
 9         for(int i=1;i<n;++i){
10             scanf("%d",&t);
11             t%=3;
12             ans^=t;
13         }
14         if(ans)printf("Yes
");
15         else printf("No
");
16     }
17 }