思路与算法

若任意堆大小在[a,b]内，可立即清空获胜。否则落入[a,b]的操作会给对方立即获胜，只需分析其余安全操作的和游戏。x<a时SG=0；x>b令r=x mod(a+b)。a=1时SG=r；a>1时r<a取0，a≤r<b取floor(r/a)+1，r≥b取1。异或各堆SG，非零Alice胜。

正确性说明

忽略危险落点不改变胜负：该分支对当前玩家必败，有限局面可按总石数归纳。安全单堆mex在一个周期内按滑动窗口归纳：r<a缺0，中段已有0、1及所有较小标签但缺floor(r/a)+1，末段含0而缺1；起始安全区间与周期边界一致，a=1单列。Sprague-Grundy定理给出和游戏异或结论。

复杂度

每堆常数运算，读入及处理O(总堆数)，辅助空间O(1)，每组异或初始化O(1)。

易错点

立即清空获胜优先于异或，不能把[a,b]当普通终态SG。a=1公式单列，a+b及堆值用64位。x<a是不能操作的安全堆。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        long long a, b;
        cin >> n >> a >> b;
        bool instant = false;
        long long nim = 0;
        while (n--) {
            long long x;
            cin >> x;
            if (a <= x && x <= b) {
                instant = true;
                continue;
            }
            if (x < a)
                continue;
            long long z = x % (a + b), g;
            if (a == 1)
                g = z;
            else if (z < a)
                g = 0;
            else if (z >= b)
                g = 1;
            else
                g = z / a + 1;
            nim ^= g;
        }
        cout << (instant || nim ? "Alice" : "Bob") << '\n';
    }
}