F. Stone 题解(对称博弈)

题目链接

题目思路

这个写法感觉有点天才，当作记录一下吧

其实越复杂的博弈好像其实最后的结论越简单？

放下官方题解

题意：轮流拿石头，每个人先确定一个上次选的数字的因数

s，然后再选择若干堆同时拿走 s 个石头，问先手有多少种

第一步的方案数使得先手必胜。

考虑这样一种局面：存在某堆石头的数量是奇数。那不管是

先手还是后手，选择 s = 1(奇数) 先把所有堆变成偶数个，

然后对手也只能 s = 1(奇数)，模仿对面拿法即可。

换言之，如果所有堆都是偶数，则不管是谁都不能选 s 为奇

数，否则变成前面一种情况，对手必胜。即 s 只能为偶数，

此时堆数量 / = 2，转化为相同的问题。

那么一直除以 2，总会在某个时候出现某个石头堆有奇数

个，转换为前面的局面。

此时答案为 (最小奇数+1)/2。

代码

#include
#define fi first
#define se second
#define debug cout<<"I AM HERE"<