题解 | #【模板】扩展巴什博弈#

由于这是一个单一堆的博弈，不需要完整的 Sprague-Grundy 函数（XOR 和），仅需通过找规律推导 必胜态（N-position） 和 必败态（P-position） 的分布周期即可。

定义状态为剩余石子数 。

• P态（必败）：当前局面的玩家注定失败（前提是对手走最优策略）。
• N态（必胜）：当前局面的玩家存在至少一种走法，能够将局面转移给对手，且转换后的局面是 P 态。

传统的巴什博弈（取 ）的周期是 。本题增加了下限 。我们可以假设周期为 。

让我们验证模 的假设： 令 。 对于任意石子数 ，设 。

• 假设 1：若 ，为 P态（必败）。

  • 证明：
    • 若 ，显然无法操作，必败。
    • 若 且 （即 处于某个周期的开头段），玩家能做的操作是减去 。
    • 操作后，剩余石子 。
    • 在模 系统下，。
    • 由于 且 ，减去 后，结果会“跨越”到上一个周期的后半段。推导表明，无论选哪个合法的 ，转移后的状态模值必然落在 范围内（即由P态只能走向N态）。对手获得了必胜态。
  • 结论：若当前模值在 ，先手无路可走或只能送给对手优越局面，为 NO。

• 假设 2：若 ，为 N态（必胜）。

  • 证明：
    • 我们需要证明存在至少一种取法 ，使得取完后的石子数 ，其中 （即转移给对手 P态）。
    • 当前模值 。
    • 我们需要 落入 （逻辑上，或者落入更低周期的同余区间）。
    • 显然，取 （其中 ）是可行的。
    • 因为 ，且 ，我们可以控制 的大小在 范围内，从而精确地将剩余石子数的模值控制在 之间。
  • 结论：若当前模值在 ，先手必胜，为 YES。

最终结论

博弈结果呈现以 为长度的周期性分布：

• 前 个状态（余数 到 ）为必败。
• 后 个状态（余数 到 ）为必胜。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        ll n, l, r;
        cin >> n >> l >> r;

        ll k = n % (l + r);
        if (k < l) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
    }
}