#10247. 「一本通 6.7 练习 4」S-Nim 题解

题目理解

这是一个组合游戏问题：

• 有 $n$ 堆石子，每堆 $a_i$ 个
• 每次可以从任意一堆中取走石子，但取的数量必须是给定集合 $\{s_1, s_2, \cdots, s_k\}$ 中的某个数
• 无法操作者输
• 需要判断多个局面是必胜态(W)还是必败态(L)

核心算法

算法标签：博弈论 SG函数 Sprague-Grundy定理 Nim游戏变种

1. 算法理论基础

SG函数定义

对于每个状态 $i$（石子数），其SG函数值 $sg(i)$ 定义为：

$$sg(i) = \text{mex}\{sg(i - s_j) \mid s_j \leq i\}$$

其中 $\text{mex}$ 表示最小排除值（最小的非负整数不在集合中）。

Sprague-Grundy定理

对于 $n$ 堆石子的游戏，总游戏的SG值为各堆SG值的异或和：

$$SG_{total} = sg(a_1) \oplus sg(a_2) \oplus \cdots \oplus sg(a_n) $$

• 如果 $SG_{total} = 0$：必败态(L)
• 如果 $SG_{total} \neq 0$：必胜态(W)

2. 代码实现分析

预处理SG函数

void calc(vector<int> &v) {
    sg[0] = 0;  // 0个石子是必败态
    
    for (int i = 1; i < N; i++) {
        appear.assign(N, false);  // 重置标记数组
        
        // 遍历所有可能的取法
        for (int j = 1; j < v.size(); j++) {
            if (i - v[j] >= 0)
                appear[sg[i - v[j]]] = true;  // 标记可达状态的SG值
            else
                break;  // 由于排序，后面的v[j]更大，直接退出
        }
        
        // 计算mex值
        for (int j = 0; j < N; j++)
            if (!appear[j]) {
                sg[i] = j;
                break;
            }
    }
}

算法标签：动态规划 mex计算 状态转移

处理查询

for (int i = 1; i <= m; i++) {
    cin >> n;
    int Xor = 0;
    
    for (int j = 1, x; j <= n; j++) {
        cin >> x;
        Xor ^= sg[x];  // 计算总异或和
    }
    
    cout << (Xor ? 'W' : 'L');  // 根据异或和判断胜负
}

算法标签：异或运算 局面判断 多组查询

3. 关键优化

1. 输入排序：

   sort(v.begin() + 1, v.end());
   

   使得在内层循环中可以提前退出，减少不必要的计算。

2. 数组复用：

   appear.assign(N, false);
   

   重复使用标记数组，避免频繁内存分配。

3. 范围限制： 由于 $a_i \leq 10^4$，预处理 $N = 10^4 + 5$ 的SG函数即可。

复杂度分析

• 预处理：$O(k \times N)$，其中 $N = 10^4$
• 每次查询：$O(n)$
• 总复杂度：$O(T \times (kN + \sum n))$，在数据范围内可行

算法标签总结

主要标签

• SG函数 - 核心计算方法
• Sprague-Grundy定理 - 多堆游戏的胜负判断
• Nim游戏变种 - 问题分类

技术标签

• mex运算 - 计算SG函数的关键
• 动态规划 - SG函数的递推计算
• 异或运算 - 多堆游戏的组合

优化标签

• 预处理 - 预先计算所有状态的SG值
• 输入排序 - 优化内层循环效率
• 数组复用 - 减少内存操作

博弈论标签

• 必胜必败态 - 游戏状态分类
• 组合游戏 - 问题类型
• impartial game - 公平组合游戏

样例验证

对于样例第一组：

s = {2, 5}
局面1: {5, 12} → sg[5]⊕sg[12] = ?⊕? = 0 → L
局面2: {2, 4, 7} → sg[2]⊕sg[4]⊕sg[7] ≠ 0 → W  
局面3: {2, 3, 7, 12} → sg[2]⊕sg[3]⊕sg[7]⊕sg[12] ≠ 0 → W
输出: LWW

这个解法通过SG函数预处理和Sprague-Grundy定理，高效解决了受限取石子游戏的胜负判断问题。