关键思路

1.单堆游戏的 SG 函数

考虑单堆硬币，从上到下编号 $1$ 到 $m$。每次操作选择某个颜色的硬币，移除它和上面的所有硬币。 这相当于：选择位置 $i$（$1 \le i \le m$），若该位置硬币颜色匹配当前玩家，则移除 $1 \dots i$ 的所有硬币。 这是一个取石子游戏的变种，每个位置对应一个可选移动。

2.单堆 SG 值的计算

对于硬币串 $S$（长 $m$），递归计算：

空堆：SG = 0

对每个位置 $i = 1 \dots m$：

若 $S[i]$ 是蓝色，是 Natalia 的可选操作，移除后剩下 $i+1 \dots m$

若 $S[i]$ 是红色，是 Cezary 的可选操作，移除后剩下 $i+1 \dots m$

注意这是非对称游戏（Partizan Game），公平状态要求无论谁先手，后手必胜。

3.公平条件的转化

定义单堆 $p$：

$win_N(p)$ = Natalia 先手时是否能赢

$win_C(p)$ = Cezary 先手时是否能赢

递归关系：

$win_N(S) = \bigvee_{i=1}^m [S[i] = N \land \lnot win_C(S[i+1..m])]$

$win_C(S) = \bigvee_{i=1}^m [S[i] = C \land \lnot win_N(S[i+1..m])]$

公平单堆：$win_N(p) = False$ 且 $win_C(p) = False$

4.多堆组合

多堆游戏：

$win_N(p_1, \dots, p_d)$ = 存在 Natalia 在某堆的合法移动，使移动后 $win_C(\dots) = False$

$win_C(p_1, \dots, p_d)$ = 存在 Cezary 在某堆的合法移动，使移动后 $win_N(\dots) = False$

公平状态要求：

Natalia 先手时无必胜策略

Cezary 先手时无必胜策略

5.实际解法

预处理所有 $2^m$ 种硬币串的 $(win_N, win_C)$，分类：

$cntF$: 公平单堆数量

$cntA$: 仅 Natalia 先手必胜的数量

$cntB$: 仅 Cezary 先手必胜的数量

$cntAB$: 双方先手都能赢的数量

多堆公平通常要求 $A$ 类堆数 = $B$ 类堆数（对称性）。

6.算法框架

动态规划：$dp[a][b]$ = 用 $a$ 个 $A$ 类堆和 $b$ 个 $B$ 类堆组成公平局面的方案数。 固定前 $k$ 堆的类型分布，DP 计算剩余堆的分配方案。

复杂度：预处理 $O(m \cdot 2^m)$，DP $O(n^3)$，可接受。