题意简述

有 $n$ 堆石子，每次操作选择 $k\;(1\le k\le n/2)$，移除 $k$ 堆，再将另外 $k$ 堆各自分裂成两个质数堆。无法操作者输。判断先手胜负。

关键性质

游戏的核心是每堆石子能否被“分裂”成两个质数。定义以下布尔数组（值域 $2\times10^5$）：

• isWinning[x]：表示一个大小为 $x$ 的石子堆是否是“必胜堆”（在某个组合意义下）。
• isGoodPosition[x]：表示 $x$ 是否为一个“好位置”。

预处理分为几步（利用 bitset 优化）：

1. 用埃氏筛标出所有合数 isComposite。
2. 对于每个奇数 $i$，计算其连续减 $2$ 的质数链长度，若长度为奇数，则 $i$ 为“必胜态”，记为 isWinning[i]。若 $i$ 本身是质数且不是必胜态，则它是“质数输状态”isPrimeLosing[i]。
3. 将 $4$ 直接记为必胜态。
4. 利用 bitset 的移位操作：将所有“质数输状态”的影响传播到更大的数上，更新 isWinning。
5. 找出所有奇质数且 isWinning 为真的位置，记为 isPrimeWinning。
6. 再次利用移位，生成 isGoodPosition：若 $i$ 为“质数胜状态”，则 $i$ 加上任意“质数胜状态”得到的数也是“好位置”。

胜负判断

对每组数据，统计所有的 $a_i$ 中：

• totalWinning = isWinning[a_i] 的总数；
• totalGood = isGoodPosition[a_i] 的总数。

结果：

• 若 totalWinning <= n - (n mod 2)，则 totalWinning 不为 $0$ 时 Alice 胜，否则 Bob 胜。
• 否则，若 totalGood 存在且 totalGood < n，Alice 胜；否则 Bob 胜。

（该结论可通过对游戏状态的组合分析得出，详见官方题解或相关推导。）

复杂度

预处理：利用 bitset 进行质数筛和移位操作，复杂度 $O(N \log N)$，其中 $N=2\times10^5$。
每组询问：$O(n)$ 统计，总复杂度 $O(N\log N + \sum n)$，足以通过。

参考代码

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

const int MAX_N = 200000 + 5;
bitset<MAX_N + 1> isComposite, isWinning, isPrimeLosing, isPrimeWinning, isGoodPosition;

void initialize() {
    isComposite[1] = true;
    for (int i = 2; i <= MAX_N; i++)
        for (int j = 2 * i; j <= MAX_N; j += i)
            isComposite[j] = true;

    for (int i = 3; i <= MAX_N; i += 2) {
        int count = 0, j = i;
        while (!isComposite[j - 2]) {
            count++;
            j -= 2;
        }
        isWinning[i] = count % 2;
        isPrimeLosing[i] = !isComposite[i] && !isWinning[i];
    }
    isWinning[4] = true;

    for (int i = 3; i <= MAX_N; i += 2)
        if (isPrimeLosing[i])
            isWinning |= isPrimeLosing << i;

    for (int i = 1; i <= MAX_N; ++i)
        isPrimeWinning[i] = (i % 2) && isWinning[i] && !isComposite[i];

    for (int i = 3; i <= MAX_N; i += 2)
        if (isPrimeWinning[i])
            isGoodPosition |= isPrimeWinning << i;
}

void solve() {
    int n, x, totalWinning = 0, totalGood = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        totalWinning += isWinning[x];
        totalGood += isGoodPosition[x];
    }
    if (totalWinning <= n - n % 2)
        cout << (totalWinning ? "Alice" : "Bob") << "\n";
    else
        cout << (totalGood && totalGood < n ? "Alice" : "Bob") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    initialize();
    int t;
    cin >> t;
    while (t--)
        solve();
}