题目分析：
这是一个经典的Multi-SG游戏的问题。
相较于普通的Nim游戏，该游戏仅仅是多了拆成两堆这样的一个状态。即多了一个SG(x+y)的过程。
而根据SG定理，SG(x+y)这个游戏的结果可以拆成SG(x)和 SG(y)游戏的结果的xor。
因此，在我们求SG函数的过程中，我们只需要再枚举一下拆成两堆的状态，即可获得Multi-SG游戏每个状态的SG函数。
但是题目中的数据范围较大（达到了1e5的级别），因此我们考虑先打表找规律。打出SG函数后不难发现，存在规律：
顺着上面的规律即可求出每一个状态的SG函数，最后将这些SG函数结果全都xor起来即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 100;
typedef long long ll;
ll n, a[N];
string Answer[2] = { "Alice
","Bob
" };
ll gsg(int x) {
if (x % 4 == 0)return x - 1;
else if (x % 4 == 3)return x + 1;
else return x;
}
int main() {
//freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
ll cnt = 0;
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
cnt ^= gsg(a[i]);
}
if (cnt == 0)cout << Answer[1];
else cout << Answer[0];
}
}
SG打表代码：
//SG打表的代码
const int maxn = 105;
int vis[maxn];
int sg[maxn];
void init() {//SG函数打表
for (int i = 0; i < 100; i++) {//枚举100个状态
memset(vis, 0, sizeof(vis));
for (int j = 1; j <= i; j++) {
vis[sg[i - j]] = true;
}
for (int j = 1; j < i; j++) {//枚举分成两块的状态
vis[sg[j] ^ sg[i - j]] = true;
}
for (int j = 0;; j++) {
if (!vis[j]) {
sg[i] = j;
break;
}
}
}
for (int i = 0; i < 100; i++) {
cout << i << " " << sg[i] << endl;
}
}