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

便于分析的定义：

• 必胜态(记为N-position)：做出最优决策，必然胜利的状态
• 必败态(记为P-position):做出任何决策无法胜利的状态

形式化的，有定义：

1. 无法移动的状态为P
2. 存在移动可以到达到P的状态为N
3. 任意移动都会到N的状态为P

注：需要将游戏考虑为一个状态图，状态指当前局面和下一步的玩家，特别的，对于这类公平组合游戏，状态图是DAG。N-position指 Next play win，即先手必胜；P-position指 Previous player win，即后手必胜。

基于以上定义，考虑题给的扩展巴什博弈，状态被量化为当前石子数量。

• 为P
• 可取个移动到P，故为N
• 移动任意步数()到达范围为（左端点减最大，右端点减最小得到），全为N，故为P

后面的讨论完全同理，都是长度为的两种区间交替，因此只需要将模，即可得到上述的前两种情况，小于为P，否则为N

参考资料

• https://www.cnblogs.com/Khada-Jhin/p/9609561.html
• https://oi-wiki.org/math/game-theory/impartial-game/

AC代码

注：最好开快读以及将endl改为'\n'，本题的IO开销很高

#include <iostream>
using namespace std;

void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    if (n % (l + r) < l) {
        cout << "NO" << '\n';
    } else {
        cout << "YES" << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}
// 64 位输出请用 printf("%lld")