很明显是nim游戏,考虑到数据量,我们无法老老实实的求解sg值。
于是我选择打表找规律。
老老实实地打到sg[100]
我们就发现了规律。
sg[i] i为偶数时sg[i]=i/2
i为奇数时,如果sg[i-1]为偶数(此时i-1为偶数)那么sg[i]=sg[i-1]/2
如果sg[i-1]为奇数时,sg[i]=sg[i/2] (向下取整)

ok初始条件为sg[1]==0(边界)那么我们就可以递归求解了。
我们观察上述规律发现每次至少/2。而事实上很可能更快,所以复杂度应该小于O(nlogn)
##代码如下:

#include<iostream>
#include<algorithm>
using namespace std;
int rsg(int x) {
    if (x == 1)return 0;
    if (x & 1) {
        if ((x >> 1) & 1)
            return rsg(x >> 1);
        else
            return x >> 2;
    }else return x >> 1;
}

int main() {
    int T;cin >> T;
    for (int tcase = 1;tcase <= T;++tcase) {
        int n;cin >> n;
        int ans = 0;
        for (int i = 1;i <= n;++i) {
            int tmp;cin >> tmp;
            tmp = rsg(tmp);
            ans ^= tmp;
        }cout << "Case " << tcase << ": ";
        ans > 0 ? cout << "Alice\n" : cout << "Bob\n";
    }
}