E. Prime Gaming

这是问题的简单版本。版本之间的区别在于，在这个版本中，$m \leq 2$。只有解决了所有版本的问题，你才能进行hack。

一个有效的配置被定义为 $n$ 堆石子的排列，使得：

每堆石子的数量是介于 1 和 $m$ 之间（包括 1 和 $m$）的整数。 给定一个由 $n$ 堆石子组成的有效配置，从 1 到 $n$ 的一些索引被标记为好的。Alice 和 Bob 开始玩一个游戏，轮流进行 $n-1$ 轮，Alice 先手。在每一轮中，他们必须执行以下操作：

选择任意一个整数 $i$，使得 $1\leq i \leq p$（其中 $p$ 是剩余的石子堆数）并且 $i$ 是好的，然后完全移除第 $i$ 堆石子。 注意，执行一次操作后，石子堆的数量减少 1，剩余的石子堆会重新索引。当只剩下一堆石子时，游戏结束。保证索引 1 总是好的。

设 $x$ 表示最后剩余的石子堆中的石子数量。Alice 想要最大化 $x$，而 Bob 想要最小化它。Alice 和 Bob 都以最优方式进行游戏。

找出所有可能的有效配置中 $x$ 的总和，对 $10^9+7$ 取模。

题解

方法

对于 $m \leq 2$，我们可以利用堆的可能值数量少这一特点，使用动态规划来解决问题。

关键观察

1. 游戏结构：

   • 每堆石子可以有 1 或 2 个。
   • 游戏通过在每一轮中移除一个“好的”堆来进行，Alice 和 Bob 交替进行。
   • 目标是最大化（对于 Alice）或最小化（对于 Bob）最后剩余堆中的石子数量。

2. 状态表示：

   • 设 dp[i][mask][player] 表示当前玩家的最优最终堆值，其中：
     • $i$ 是剩余的堆数。
     • mask 编码了配置：每个位表示一堆有 1（0）或 2（1）个石子。
     • player 为 0 表示 Alice 的回合，1 表示 Bob 的回合。

3. 转移：

   • 对于每个状态，尝试移除每个可能的“好的”堆，并相应地更新状态。
   • Alice 将选择最大化最终堆值的移动，而 Bob 将最小化它。

4. 计算：

   • 枚举所有有效配置，并使用 DP 模拟游戏。
   • 对所有配置的最优最终堆值求和。

对于 $m > 2$

对于困难版本（$m > 2$），问题可以通过考虑值高于或低于某个阈值的位置，将其简化为 $m = 2$ 的情况。这种简化的细节更为复杂，可以通过比较两个版本的代码来找到。

参考资料

• E1 提交 (简单版本)
• E2 提交 (困难版本)