F. Stone
原题链接(gym)：F. Stone
Tag：博弈
题目大意
一开始有 \(n\) 堆石子，每堆石子有 \(a_i\) 个石子， 两个玩家轮流取石子， 取石子的过程是，先挑选若干个满足个数的石子堆， 每次每个玩家取的石子必须是上一个人所取的石子数的因子。 即，我们设先手玩家第一轮取了 \(s_1\) 个石子， 后手玩家取 \(s_2\) 石子， 那么 \(s_1\) 和 \(s_2\) 数字必须满足 \(s_1\) 是 \(s_2\) 的倍数 。 当一方不能取石子的时候就输掉了游戏。
问：先手在必胜的条件下，第一回合有多少种取石子的方案。
数据范围：
\(1\le n\le 10^6\)，\(1\le a_i\le 10^9\)。
分析
首先很显然这道题是一个博弈论， 我们先从只有一堆石子开始考虑这个问题。
首先我们假设这一堆石子有奇数个， 有一个显而易见的结论， 如果先手只取一个，那么后手也只能取一个， 这样一来先手就是必胜的。 因此我们得出第一个结论：
接下来我们尝试把这个结论推广到多个石子堆， 我们考虑奇偶的关系，我们会发现， 先手可以把所有的奇数堆都取一个， 后手面对的就是全都是偶数堆的情况， 并且由于先手取了奇数个，他也必须取奇数个， 这样就又给先手创造出来了有奇数堆的条件， 如此循环往复，后手是无论如何都赢不了游戏的。 由此我们得出了第二个结论：
考虑出了什么是必胜态之后我们来考虑非必胜态， 根据结论 \((2)\)，很显然所有石子堆都是偶数的时候是没有必胜态的。 那么考虑到结论 \((2)\)，在这种情况下谁都不会去取奇数个， 由此我们得出了结论：
那么接下来我们假设一个状态： \(a_i\)、\(last\)、\(val\)。 在这个状态中的三个变量分别代表， 每一堆石子有多少石子、 上一个取的人是谁、上一个人取了多少个。 由于我们已经得出了结论 \((3)\)， 那么当 \(a_i\) 全部都为偶数的时候没有人会取奇数个。 那么我们大胆地把这个状态变成： \(2 \times a_i\)、\(last\)、\(2 \times val\)。 那么在这个时候我们会发现这个状态没有任何性质上的不同。 如果我们把乘以二之前的状态 \(\text{DAG}\) 称为 \(G_1\)， 乘以二之后的状态 \(\text{DAG}\) 称为 \(G_2\)， 我们会发现这两个 \(\text{DAG}\) 上是可以创造一个双射关系的， 也就是说这两个状态是等价的， 于是又可以得出一个结论：
那么因为这两个 \(\text{DAG}\) 是建立了双射关系的， 因此我们可以从结论 \((4)\) 进一步得出一个最重要的结论：
那么有了结论 \((5)\)，我们就可以做这道题了， 因为我们不断把一个全是偶数的状态除以 \(2\) 之后， 其一定会出现一个状态存在一个奇数，这样我们就可以找到一个必胜态了。
我们考虑到，实际上我们不断对一个数字除以 \(2\) 的过程， 实际上和用一个数字除以它的 \(lowbit\) 是等价的。 因此我们可以直接考虑 \(lowbit\)。
那么我们再去思考一下，对于一个必胜态而言， 我们有多少种取值的方法呢？ 对于一个奇数，如果我们要取其中的奇数个， 我们有 \((奇数个数 + 1) / 2\) 种取出奇数的方法。
那么最后我们的写代码思路就是， 先找出 \(lowbit\) 最小的值， 然后看当他被不断除以二变成奇数之后我们有多少种取值， 其中不断除以二的过程我们可以直接用 \(x / lowbit(x)\) 来计算。
代码实现
void NeverSayNever() {
int n; cin >> n;
vector<int> vec(n);
for(auto &x : vec) cin >> x;
vector<int> tmp(n);
for (int i = 0; i < n; ++i) {
tmp[i] = lowBit(vec[i]);
}
int mi = *std::min_element(tmp.begin(), tmp.end());
vector<int> tmp1;
for (int i = 0; i < n; ++i) {
if(tmp[i] == mi){
tmp1.push_back(vec[i]);
}
}
int ans = *std::min_element(tmp1.begin(), tmp1.end());
cout << (ans/lowBit(ans) + 1) / 2 << endl;
}
额外思考
这道题个人感觉下来，绝大部分是显然的， 最难的一部分是考虑到除以二的操作。 至于把状态当成点，操作当成边， 把一个博弈过程中的所有状态变成一个 \(\text{DAG}\)， 感觉在博弈论中是非常常见的。 综合来说感觉是一道十分巧妙的博弈论。
日志
本页面创建于 2024/6/25 17:10 UPD-1：2024/6/27 20:01 格式修正
特别鸣谢：
tarjen 在地铁上推荐了这道题
Kilo_5723 提供的指导