洛谷6665 [清华集训2016] Alice 和 Bob 又在玩游戏
Luogu UOJ 分析 考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。 于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。 如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。 如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG ...
Luogu UOJ 分析 考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。 于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。 如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。 如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG ...
Luogu 分析 首先发现这是个 Multi-SG 游戏，那么可以考虑使用 SG 函数。 先考虑怎么暴力求 $SG(x)$ 。 大力枚举分成的堆数。如果将 $x$ 分成了 $i$ 堆，那么这 $i$ 堆中有 $x\bmod i$ 堆 $\left\lceil\frac{x}{i}\right\rceil$，有 $i-x\bmod i$ 堆 $\left\lfloor\frac{x}{i}\r...