「星际迷航」题解

核心思路

1. 单树博弈分析

定义节点 $u$ 的 SG 值：

• 叶子节点：$SG(u) = 0$
• 内部节点：$SG(u) = \bigoplus_{v \in \text{children}(u)} (SG(v) + 1)$

$SG(1) > 0$ 表示在单树游戏中先手必胜。

2. 星门的影响

星门从 $u$ 到 $w$ 相当于给 $u$ 增加虚拟子节点：

$$SG'(u) = SG(u) \oplus (SG(w) + 1)$$

3. 方案计数

设：

• $X = \#\{x \mid SG(x) = 0\}$（必败节点数）
• $Y = N - X$（必胜节点数）
• $Z = \#\{x \mid SG(1) \oplus (SG(x) + 1) > 0\}$（$A_i=1$ 时能赢的 $B_i$ 个数）

4. 矩阵递推

定义状态向量：

$$\mathbf{v}_i = \begin{bmatrix} F_i \\ G_i \end{bmatrix} $$

其中 $F_i$ 为从宇宙 $i$ 开始必胜的方案数，$G_i$ 为必败的方案数。

递推矩阵：

$$\mathbf{M} = \begin{bmatrix} (N-1)N\cdot [SG(1)>0] + Z & (N-1)N\cdot [SG(1)>0] + W \\ (N-1)N\cdot [SG(1)=0] + W & (N-1)N\cdot [SG(1)=0] + Z \end{bmatrix}$$

其中 $W = N - Z$。

最终答案：

$$\mathbf{v}_0 = \mathbf{M}^D \cdot \mathbf{v}_D, \quad \mathbf{v}_D = \begin{bmatrix} [SG(1)>0] \\ [SG(1)=0] \end{bmatrix} $$

时间复杂度：$O(N + \log D)$。