Readme

2029.Stone-Game-IX

本题其实是决策推理。我们要分析出以下几种对策。

1. 如果存在被3整除的元素，一定选它。对于当前需要做决策的选手而言，显然目前的sum不会被3整除（否则上一轮对手决策完就输了）。此时如果剩下有被3整除的元素X，那么选它总不会错。如果你选了，你就可以安全地把问题转移给对手。如果你不选，侥幸你能通过其他方法把问题转移给对手，对手依然可以通过选X从而把问题安全地转移给你。所以优先选择X，既可以保证自己该轮安全，也可以让对手少一个自保安全的机会，何乐而不为？

2. 如果当前的sum被3除余1，在排除了方案1的可能性后，当前选手只能在剩下的元素里也找一个被3除余1的；否则选被3除余2的元素的话，一定会导致sum被3整除，从而失败。显然，如果剩下的元素里没有被3除1的，那么必败。

3. 同上，如果当前的sum被3除余2，在排除了方案1的可能性后，当前选手只能在剩下的元素里也找一个被3除余2的；否则选被3除余1的元素的话，一定会导致sum被3整除，从而失败。显然，如果剩下的元素里没有被3除2的，那么必败。

4. 此外还有一条规则。如果当前做决策的选手没有剩余元素可选，无论该轮是谁，都宣告Alice获胜。

综上所述，Alice作为先手，它的第一步只可能是选一个被3除余1，或者被3除余2的元素。一旦第一步确定后，接下来双方的所有决策，其实都是确定性的，不存在分叉。即选完被3整除的元素之后，只能一直取余数固定的一类元素，直至该元素取完：此时如果还有其他元素，则判当前选手失败；否则判Alice赢。