题目大意

这是一个基于公平组合游戏的博弈论问题。游戏规则如下：

• 给定一个阈值 $F$，有 $T$ 组游戏
• 每组游戏有 $N$ 堆石子，每堆 $a_i$ 个
• 玩家轮流操作，每次选择一堆石子（数量 $\ge F$）和一个整数 $M \ge 2$
• 将这堆石子分成 $M$ 堆，要求分得尽量平均（最多一堆比最少一堆多1）
• 无法操作（所有堆石子数 $< F$）的玩家输掉游戏
• 小A的对手先手，小A后手

需要判断每组游戏的胜者，输出 1 表示先手胜，0 表示后手胜。

算法思路

1. 博弈论基础

这是一个多堆公平组合游戏，可以使用 Sprague–Grundy 定理 解决：

• 整个游戏的 SG 值 = 每堆石子 SG 值的异或和
• 异或和 $\neq 0$ ⇒ 先手必胜
• 异或和 $= 0$ ⇒ 后手必胜

2. 单堆 SG 函数计算

定义 $SG(x)$ 为一堆数量为 $x$ 的石子的 Grundy 值：

• 如果 $x < F$，不能操作，$SG(x) = 0$
• 如果 $x \ge F$，枚举所有可能的操作 $M = 2, 3, \dots, x$

分堆方式

对于 $x$ 分成 $M$ 堆：

• $q = \lfloor x / M \rfloor$
• $r = x \bmod M$
• 分堆结果：$r$ 堆有 $q+1$ 个石子，$M-r$ 堆有 $q$ 个石子

后继状态 SG 值

分堆后的 SG 值为：

$$SG_{\text{new}} = [r \bmod 2 \cdot SG(q+1)] \oplus [(M-r) \bmod 2 \cdot SG(q)] $$

3. 优化技巧

数论分块

直接枚举 $M$ 会超时，利用数论分块优化：

• 对于固定的 $q = \lfloor x / M \rfloor$，$M$ 的取值范围是连续的区间
• 在每个区间内，只需检查 $M$ 和 $M+1$ 即可覆盖所有可能的奇偶组合
• 将复杂度从 $O(n^2)$ 降至 $O(n \sqrt{n})$

内存优化

• SG 值通常不会很大，使用固定大小的 visited 数组（大小1000足够）
• 避免频繁的 memset 大数组

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 100005;
const int MAX_SG = 1000;

int F, T;
int SG[MAXN];
bool visited[MAX_SG];
vector<int> results;

int main() {
    scanf("%d%d", &T, &F);
    
    for (int x = 0; x < MAXN; x++) {
        if (x < F) {
            SG[x] = 0;
            continue;
        }
        
        memset(visited, 0, sizeof(visited));
        
        for (int M = 2; M <= x; M++) {
            int q = x / M;
            int r = x % M;
            int R = x / q;
            
            int sg = 0;
            if (r % 2) sg ^= SG[q + 1];
            if ((M - r) % 2) sg ^= SG[q];
            if (sg < MAX_SG) visited[sg] = true;
            
            if (M + 1 <= R) {
                r = x - (M + 1) * q;
                sg = 0;
                if (r % 2) sg ^= SG[q + 1];
                if ((M + 1 - r) % 2) sg ^= SG[q];
                if (sg < MAX_SG) visited[sg] = true;
            }
            
            M = R;
        }
        
        int mex = 0;
        while (mex < MAX_SG && visited[mex]) mex++;
        SG[x] = mex;
    }
    
    for (int t = 0; t < T; t++) {
        int N;
        scanf("%d", &N);
        int total = 0;
        for (int i = 0; i < N; i++) {
            int a;
            scanf("%d", &a);
            total ^= SG[a];
        }
        results.push_back(total ? 1 : 0);
    }
    
    for (size_t i = 0; i < results.size(); i++) {
        printf("%d", results[i]);
        if (i < results.size() - 1) printf(" ");
    }
    printf("\n");
    
    return 0;
}

复杂度分析

• 预处理：每个 $x$ 的处理复杂度为 $O(\sqrt{x})$，总复杂度 $O(\max a_i^{1.5})$，在 $10^5$ 数据范围内可接受
• 查询：每组游戏 $O(N)$
• 空间：$O(\max a_i)$