GAME-24 J K
J-受限制 Nim 2
https://atcoder.jp/contests/game-24/tasks/game_j
有点难，首先要想到削减石子等价于让差分始终非负，可以发现实际上是让除了第一堆石子以外的 差分在相邻堆之间移动。
移动的过程 其实是 阶梯形 Nim 游戏，其结论是： 假设 0 - index，如果偶数位置的 nim 和是 0 那么 先手必败。
阶梯形nim 游戏的规则是 ：你可以选择拿走 第一堆 的石子任意颗，或者 移动 i 位置的 石子 到 i - 1 位置。
那么显然有，奇数位置上的石子移动到偶数上的时候，对手可以毫无顾忌的直接移动到下一个奇数位置，这样一来，奇数位置上的棋子，不会影响偶数位置的选择。
而为什么偶数位置决定了后手的胜率呢？因为 先手移动偶数位置的时候，如果 偶数为 nim 和是 0，就意味着 后手总有应对。所以如果 nim 和是 0，后手总能让 最终 偶数位置的 数字归于其 等价类 0 0 0 0 0 0 ...
于是如果 偶数位置上 nim 和是 0，后手必胜。
而这个题的 奇偶 是 反过来看的，因为 你 移除 前面一个堆的 石子的时候，等价于 前面一个差分 的 差分值 移动到 后面一个差分上，所以是反过来的。
namespace XK {
void solve() {
ll N; rd(N);
V<ll> A(N); rd(A);
rrep(i, 0, N - 1) {
A[i + 1] -= A[i];
}
debug(A);
ll ans = 0;
for(int i = N - 1; i >= 0; i -= 2)
ans ^= A[i];
wt(ans ? "Alice" : "Bob");
}
};K - 四连形里的多米诺 2
https://atcoder.jp/contests/game-24/tasks/game_k
该题目需要了解组合博弈的内容：
组合博弈的核心是：把局面表示成“双方能走到哪些局面”，求出可以组合运算的博弈值，再判断胜负。
1. 用 ({L\mid R}) 描述局面
[ G={\text{Alice 一步能到达的局面}\mid \text{Bob 一步能到达的局面}}. ]
Alice、Bob 是固定玩家身份，不是先手、后手。以下都采用“无法操作者输”的规则。
| 博弈值 | 含义 |
|---|---|
| (0={\mid}) | 双方都不能动 |
| (1={0\mid}) | Alice 独享一步 |
| (-1={\mid0}) | Bob 独享一步 |
| (\frac12={0\mid1}) | 一个普通数值博弈，分数不是胜率 |
| (*={0\mid0}) | 双方都能走到零，先手赢 |
并非所有博弈值都是普通数字，也不能对左右选项取平均数。
2. 游戏可以相加、取负、判等
-
(G+H)：把两个独立组件放在一起，每回合只选一个操作。
-
对于 (G+H)，每一步只能选一个组件操作，另一个保持不变：
[ \boxed{ G+H= {G^L+H,\ G+H^L \mid G^R+H,\ G+H^R} } ]
其中 (G^L) 等符号代表相应的所有合法后继；没有合法操作的项就不列。
因此可以按三步理解：
- 枚举 Alice 能在哪个组件操作，把操作后的整个局面写在左边。
- 枚举 Bob 的操作，把结果写在右边。
- 对这些后继局面继续递归计算、化简。。
-
-
(-G)：递归交换双方身份。
-
(G=H)：在任意其他组合游戏中，两者都能相互替换，不改变胜负；不要求游戏树相同。
因此：
[ G+(-G)=0. ]
**单独玩时胜负相同，不代表博弈值相等。**它们与其他组件组合后的表现可能不同。
3. 博弈值与零有四种关系
| 关系 | 胜负 |
|---|---|
| (G>0) | Alice 无论先后手都赢 |
| (G<0) | Bob 无论先后手都赢 |
| (G=0) | 后手赢 |
| (G\parallel0) | 与零不可比，先手赢 |
例如：
[ *\ne0,\qquad +=0. ]
4. Nim 与 SG 是其中的特殊情况
一堆 (n) 枚石子的 Nim，博弈值记为 (*n)，称为 nimber。星号不是乘号：
[ *2\ne2,\qquad *2\ne +. ]
nimber 的游戏加法对应下标异或：
[ *a+b=(a\oplus b). ]
有限、不偏、正常规则游戏都等价于某个 nimber：
[ G=*SG(G), \qquad SG(G)=\operatorname{mex}{SG(H):G\to H}. ]
SG 类似 DP，mex 是后继值中缺失的最小非负整数。SG 是等价 Nim 堆大小，不是优势评分；值越大不代表越容易赢。
5. 一般博弈不能全部套异或
例如：
[ h={1\mid-1} ]
不是 nimber。Alice 操作它得到 (1)，Bob 操作它得到 (-1)。它虽然也满足 (h+h=0)，但仍不等于 (*)。
计算时要先辨认值的类型：
- 普通数值：按普通算术相加。
- nimber：下标异或。
- 其他博弈值：保留左右选项，用博弈等价关系化简。
于是我们可以写出每个方块对应的组合博弈值：
| 方块 | 博弈值 |
|---|---|
| A | (-2) |
| B | (2) |
| C | (-\frac12) |
| D | (\frac12) |
| E | (e={0\mid0}=*) |
| F | (f={0\mid-1}) |
| G | (g={1\mid0}) |
| H | (h={1\mid-1}) |
于是可以看出有：
e + e = 0, h + h = 0, f = -g, f = g + (-1)
最后两个需要解释一下，f = -g 指的是，f 等价于 g 中两方交换，-g = {- 0| - 1}，交换 | 两边且取反； f = g + (-1) 的意思是，考虑 g + (-1) 这个组合选择一次之后的结果，有：
| 谁操作 | 操作哪个组件 | 操作后的整个局面 |
|---|---|---|
| Alice | (g\to1) | (1+(-1)=0) |
| Bob | (g\to0) | (0+(-1)=-1) |
| Bob | (-1\to0) | (g+0=g) |
于是 g + (-1) = {0 | -1, g}，而留下 -1 比 留下 g 的 0 更有利，于是 可以化简为 {0 | -1}，也就是 f。
于是这里带入 得到 g - 1 = -g，得到 g + g = 1。所以
[ \begin{aligned} Ff+Gg &=F(g-1)+Gg\ &=(F+G)g-F. \end{aligned} ]
现在一共有 (F+G) 个 (g)。又因为： [ g+g=1, ]
每两个 (g) 就能化成普通数值 (1)，于是： $p = (F + G) \mod 2$
[ \boxed{ Ff+Gg= \left\lfloor\frac{F+G}{2}\right\rfloor-F +\underbrace{((F+G)\bmod2)}_{p},g. } ]
e 就是单纯 {0 | 0} 的 nimber *1
而 h 可是强大的 {1 | -1}，所以要先抢 H，判断奇偶之后看 Alice 能否获得多一轮机会，但是注意交换先后手，于是我们有答案了。
首先判断博弈值是不是正的，如果是的话就 Alice 赢，如果是 0 的话，要判断是不是最终步是 Alice 的回合，是的话赢。反之则输
namespace XK {
void solve() {
ll a, b, c, d, e, f, g, h; rd(a,b,c,d,e,f,g,h);
bool ok = 1;
ll v = 4 * (b - a) + d - c + 2 * ((f + g) / 2 - f);
if(h % 2) {
v += 2;
ok = 0;
}
if((f + g) % 2) {
if(ok) v += 2;
ok = 1 - ok;
}
if(e % 2) ok = 1 - ok;
wt((v > 0 || (v == 0 && !ok)) ? "Alice" : "Bob");
}
};