HDU1536:S-Nim游戏中的SG博弈分析

### 问题描述
Arthur 和他的妹妹 Caroll 经常玩一种名为 Nim 的游戏。Nim 游戏规则如下：
- 游戏开始时有若干堆珠子，每堆的数量不一定相同。
- 玩家轮流选择一堆并从中移除任意数量（但至少一个）的珠子。
- 无法进行任何移动的玩家输掉游戏。

Arthur 和 Caroll 发现了一个简单的必胜策略：通过异或运算计算所有堆中珠子数量的 XOR 值。如果 XOR 值为 0，则当前玩家将输掉游戏；否则，可以采取使 XOR 值变为 0 的行动。

然而，他们很快厌倦了这种完美的策略，并设计了一种新的游戏——S-Nim。在 S-Nim 中，每次只能从预定义集合 S 中选择一个数值来移除相应数量的珠子。因此，不再是所有情况下都能将 XOR 值调整为 0。

### 输入输出要求
输入包含多个测试用例，每个测试用例包括两部分：
1. 第一部分是集合 S 的定义，其中 k 表示集合大小，随后列出 k 个整数 si，表示允许移除的珠子数量。
2. 第二部分是 m 个位置评估，每行开头是一个整数 l 表示堆的数量，后面跟着 l 个整数 hi 表示每堆的珠子数量。

对于每个位置，如果它是获胜位置则输出 'W'，如果是失败位置则输出 'L'。每个测试用例后换行。

### 示例
#### 输入
```
2 2 5
3
2 5 12
3 2 4 7
4 2 3 7 12
5 1 2 3 4 5
3
2 5 12
3 2 4 7
4 2 3 7 12
0
```
#### 输出
```
LWW
WWL
```

### 实现思路
为了判断某个位置是否为获胜位置，我们使用 SG 函数（Sprague-Grundy 函数）来构造解法。SG 函数的核心思想是递归地计算每个状态下的最小非负整数，使得该状态下没有合法的转移能够到达这个值。

以下是 C++ 代码实现：
```cpp
#include
#include
#include
#include
#include
using namespace std;
int sg[10005];
int f[110];
void getsg(int n) {
memset(sg, 0, sizeof(sg));
bool hash1[10005]; // 必须用 bool 定义，不然会超时。
for (int i = 0; i <10005; i++) {
memset(hash1, 0, sizeof(hash1));
for (int j = 0; j if (i - f[j] >= 0)
hash1[sg[i - f[j]]] = 1;
}
for (int j = 0; j <10005; j++) {
if (!hash1[j]) {
sg[i] = j;
break;
}
}
}
}
int main() {
int n;
while (scanf("%d", &n) != EOF && n != 0) {
for (int i = 0; i scanf("%d", &f[i]);
sort(f, f + n);
getsg(n);
int m;
scanf("%d", &m);
for (int i = 0; i int t;
int pp;
int res = 0;
scanf("%d", &t);
for (int j = 0; j scanf("%d", &pp);
res ^= sg[pp];
}
if (res == 0)
printf("L");
else
printf("W");
}
printf("\n");
}
return 0;
}
```