题解：P14586 [LNCPC 2025] 前后缀石子博弈

· · 题解

这是本题的官方题解。

:::info[提示 1]

“取走 1 颗石子”会改变该堆的石子数的奇偶性。每轮“前后缀取石子”必然会改变“当前局面的非零的编号最小和最大的堆的石子数”中至少一个的奇偶性。

:::

:::success[结论 1]

“当前局面是必胜局面”的充要条件是“当前局面的非零的编号最小和最大的堆的石子数中，至少有一个为奇数”。（奇奇、奇偶、偶奇必胜，偶偶必败。）

若初始局面中第 1 和 m 堆的石子数中至少有一个为奇数，则输出 Alice；否则，输出 Bob。

证明：

边界情况：当前局面的所有的非零的堆的石子数都为 1 时，该玩家可以取走全部石子，对手将会失败。（必胜边界为奇奇。）

必败局面无论怎样操作，都将要么让对手面临必胜局面，要么取走 0 颗石子失败。（偶偶一定会转移到奇奇、奇偶、偶奇。）

必胜局面都可以通过下面的操作，始终让对手面临必败局面。（奇奇、奇偶、偶奇都可以转移到偶偶。）\ 将当前局面的有石子的堆从前往后编号为 1,\cdots,m'。\ 若当前局面的所有的非零的堆的石子数都为奇数，则令 \text{get}_{\text{pre}}=m',\text{get}_{\text{suf}}=0；\ 否则，记当前局面的石子数为非零偶数的堆的最小和最大编号分别为 p,s，令 \text{get}_{\text{pre}}=p-1,\text{get}_{\text{suf}}=m'-s。

:::

:::info[提示 2]

不妨拆开原问题从贡献的角度思考：a_{1,j}(1\leqslant j\leqslant put_{pre}) 会对 a_{i,1}(i\geqslant2) 产生怎样的贡献？

:::

:::success[结论 2]

证明：前/后缀和的性质，组合数上角标相同求和式 $\sum\limits_{i=y}^{x}C_i^y=C_{x+1}^{y+1}$。 ::: :::info[提示 3] 只需关心 $a_{i,1},a_{i,m}$ 的奇偶性。组合数的奇偶性。 ::: ::::success[结论 3] :::warning[Lucas 定理推论]{open} $C_{x}^y$ 为奇数 $\Leftrightarrow$ $y\subseteq x$（在二进制下，$y$ 是 $x$ 的子集。也即 $y\ \operatorname{and}\ x=y$，其中 $\operatorname{and}$ 表示按位与运算）。 证明：$C_{x}^y\equiv C_{\lfloor\frac{x}{2}\rfloor}^{\lfloor\frac{y}{2}\rfloor}C_{x\bmod 2}^{y\bmod2}\pmod 2$。$C_{0}^{0}=C_{1}^{0}=C_{1}^{1}=1,C_{0}^{1}=0$。 ::: $a_{1,j}(1\leqslant j\leqslant put_{pre})$ 会改变 $a_{i,1}(i\geqslant2)$ 的奇偶性 $\Leftrightarrow$ $a_{1,j}$ 是奇数并且 $i-2\subseteq i-2+j-1$。$a_{i,m}$ 同理。 :::: :::info[提示 4] 若使 $i-2\subseteq i-2+j-1$ 中的 $i,j$ 独立，则原问题或许可以高效解决。 ::: ::::success[结论 4] :::warning[推导]{open} $i-2\subseteq i-2+j-1$。 $\Leftrightarrow$ $(i-2)\ \operatorname{and}\ ((i-2+j-1)-(i-2))=(i-2)\ \operatorname{and}\ (j-1)=0$。 $\Leftrightarrow$ $j-1\subseteq \operatorname{not}(i-2)$，其中 $\operatorname{not}$ 表示按位取反运算。 ::: $a_{i,1}\equiv\sum\limits_{1\leqslant j\leqslant put_{pre}\land j-1\sube \operatorname{not}(i-2)}a_{1,j}\pmod 2\text{ if }i\geqslant2$。$a_{i,m}$ 同理。 :::: :::success[解法] 求出满足 $2^{bit}-1\geqslant\max(n,m)$ 的最小正整数 $bit$。令按位取反运算 $\text{not}$ 是在 $bit$ 位二进制数下的，即 $\operatorname{not}(x)=(2^{bit}-1)-x$。 预处理：对 $a_{1,j}(1\leqslant j\leqslant \text{put}_{\text{pre}})$ 求子集和（SOS）得到前缀子集和 $\text{pre\_sum}_i=\sum\limits_{j\subseteq i}a_{1,j+1}$，后缀子集和 $\text{suf\_sum}_i$同理。 对于第 $i(i\geqslant2)$ 局游戏，若 $pre\_sum_{\operatorname{not}(i-2)}$ 和 $suf\_sum_{\operatorname{not}(i-2)}$ 中至少有一个为奇数，则输出 `Alice`；否则，输出 `Bob`。 特殊处理第 $1$ 局游戏、$put_{pre}=0$ 和 $put_{suf}=0$ 的情况。 时间复杂度：$O(\max(n,m)\log \max(n,m))$。空间复杂度：$O(\max(n,m))$。 :::