问题理解

我们有一个长度为 $n$ 的棋盘，上面有 $k$ 个棋子（$k$ 为偶数），黑白相间排列：

• 最左边是白棋，最右边是黑棋
• 白棋只能向右移动，黑棋只能向左移动
• 每次可以移动 1 到 d 个棋子（不能跨越其他棋子）
• 小 A 先手移动白棋，小 B 后手移动黑棋
• 无法操作者输

要求：计算使小 A（先手）必胜的初始棋子布局总数。

---

关键观察

1. 独立子游戏分解

$k$ 个棋子将棋盘分成 $k+1$ 个空隙（间隔）：

• 第 $1$ 个空隙：最左边到第一个棋子
• 第 $2$ 个空隙：第一个棋子到第二个棋子
• ...
• 第 $k$ 个空隙：第 $k-1$ 个棋子到第 $k$ 个棋子
• 第 $k+1$ 个空隙：第 $k$ 个棋子到最右边

关键性质：
每个白棋的移动相当于减少它左边的某个空隙，增加它右边的某个空隙；黑棋同理。
但更简单的看法：将相邻棋子之间的间隔看作独立的石子堆，移动棋子相当于从某个堆中取石子。

2. 转化为 Nim 游戏

考虑相邻棋子之间的 $k-1$ 个间隔（忽略最左和最右的空隙），设这些间隔的长度为 $a_1, a_2, \dots, a_{k-1}$。

当白棋向右移动 $x$ 格时：

• 相当于从某个 $a_i$（白棋右边的间隔）中取走 $x$ 个石子，放入 $a_{i-1}$（白棋左边的间隔）
• 但这不是标准的 Nim，因为石子数总量不变，只是转移

实际上这是一个 k-1 堆的取石子游戏，但移动规则特殊。

3. 已知结论

该游戏是 公平组合游戏，且可以证明：

• 将棋子从右向左编号 $1$ 到 $k$
• 对于第 $i$ 个棋子，设它到它右边相邻棋子的距离为 $x_i$（对白棋）或到左边相邻棋子的距离为 $x_i$（对黑棋）—— 这里需要统一视角

更标准的转化： 把相邻的黑白棋子对看作一堆石子，石子数为它们之间的距离减 $1$。
这样共有 $k/2$ 堆，每次操作可以选择 $1$ 到 $d$ 堆，从每堆中取走任意正数个石子（但不能取不同堆的不同数量？需要仔细分析）。

---

实际上，这个游戏是 Moore's Nim 的变种：
每次可以从最多 $d$ 堆中取石子，每堆取的数量任意（至少 $1$）。
该游戏的必胜条件是：将每堆的石子数写成二进制，对于每个二进制位，统计该位为 $1$ 的堆数，如果 每个二进制位上的 1 的个数 mod (d+1) = 0，则先手必败，否则先手必胜。

---

问题转化

1. 建立模型

设 $m = k/2$（黑白配对的对数）。
将棋盘上的 $k$ 个棋子按位置排序：$p_1 < p_2 < \dots < p_k$，其中 $p_1$ 是白棋，$p_2$ 是黑棋，$p_3$ 是白棋，…… 颜色交替。

定义 $m$ 堆的石子数： [ b_i = p_{2i} - p_{2i-1} - 1, \quad i=1,2,\dots,m ] 这表示第 $i$ 个白棋与它右边紧邻的黑棋之间的空格数。

2. 移动规则

• 小 A（白棋）移动：选择某个 $i$，将 $b_i$ 减少 $t$（$1 \leq t \leq d$ 且 $t \leq b_i$），同时将 $b_{i-1}$（如果存在）增加 $t$
• 小 B（黑棋）移动：选择某个 $i$，将 $b_i$ 减少 $t$（$1 \leq t \leq d$ 且 $t \leq b_i$），同时将 $b_{i+1}$（如果存在）增加 $t$

这实际上是 阶梯博弈 的变种，但每次可移动 $1$ 到 $d$ 个棋子。

3. 博弈结论

经过分析（或已知结论），该游戏的 SG 函数与 Moore's Nim 等价：

• 将 $b_1, b_3, b_5, \dots$（奇数下标堆）看作独立 Nim 堆
• 但每次可以从最多 $d$ 堆中取任意正数

Moore's Nim 定理：
令 $r_j$ = 所有 $b_i$ 在二进制第 $j$ 位上为 $1$ 的堆数。
如果对于所有 $j$，$r_j \equiv 0 \pmod{d+1}$，则先手必败；否则先手必胜。

---

计数问题

我们需要计算满足以下条件的初始布局数：

1. 棋子位于 $1$ 到 $n$ 的格子上
2. 最左是白棋，最右是黑棋，相邻棋子颜色不同
3. 对应的 $m$ 堆石子数 $b_1, b_2, \dots, b_m$ 满足：不是 Moore's Nim 的必败态

1. 总布局数

棋子位置 $p_1 < p_2 < \dots < p_k$ 满足：

• $p_1 \geq 1$，$p_k \leq n$
• 颜色交替：$p_1$（白）, $p_2$（黑）, $p_3$（白）, …

等价于：选择 $k$ 个不同的格子，指定最左为白，最右为黑，中间交替。
但已知最左白最右黑且交替，实际上就是选择 $k$ 个位置，自动满足颜色要求（因为排列固定）。

更简单：设 $q_i = p_{i+1} - p_i - 1$（$i=1,\dots,k-1$）为棋子间间隔，$l = p_1 - 1$，$r = n - p_k$。

我们有： [ l + \sum_{i=1}^{k-1} q_i + r = n - k ] 其中 $l, r, q_i \geq 0$。

但我们的 $b_i$ 是 $q_2, q_4, \dots, q_{k-2}$ 吗？需要仔细对应。

实际上，已知： [ b_i = p_{2i} - p_{2i-1} - 1 ] 且 [ \sum_{i=1}^m b_i + (m-1) + \text{其他间隔} = n - k ] 经过推导，总布局数为 $\binom{n}{k}$（选择 k 个位置放棋子，颜色自动交替确定）。

2. 必败态计数

必败态条件：对所有二进制位 $j$，$\sum_{i=1}^m [b_i \& 2^j] \equiv 0 \pmod{d+1}$。

用 生成函数 + 容斥 或 数位 DP 计数：

• 设 $f_j$ 表示满足第 $j$ 位条件的方案数
• 但各位相互独立吗？不独立，因为 $b_i$ 之和受限于 $n$

标准做法：数位 DP，从高位到低位确定每个 $b_i$ 的二进制位，同时记录进位信息。

3. DP 状态设计

设 $dp[pos][carry]$ 表示：

• 当前处理到二进制第 $pos$ 位（从高到低）
• $carry$ 表示低位的进位情况（模 $d+1$）
• 值为满足条件的方案数

转移时，枚举每个 $b_i$ 在当前位的值（0 或 1），检查 1 的个数是 $d+1$ 的倍数，并计算向高位的进位。

---

算法流程

1. 数位 DP 计算必败态数

   • 状态：$dp[pos][mask]$，$mask$ 表示当前位的选择情况（可优化）
   • 从高位到低位处理，保证 $b_i$ 总和不超过 $n-k$
   • 用组合数计算满足二进制位条件的分配方案

2. 计算总布局数
   总布局数 = $\binom{n}{k}$

3. 答案计算
   必胜方案数 = 总布局数 - 必败态数

---

复杂度分析

• 数位 DP 的位数：$\log n \approx 14$
• 状态数：$O(\log n \cdot (d+1)^m)$，但 $m = k/2 \leq 50$，直接做太大
• 需要优化：利用各位独立性质，用快速幂或生成函数

实际可用 生成函数： [ F(x) = \left(\sum_{s=0}^{d} \binom{m}{s} x^s\right)^{\log n} ] 但需要处理进位和上限 $n$。

---

总结

这道题的核心是：

1. 博弈分析：将棋子布局转化为 Moore's Nim 模型
2. 必胜条件：二进制每位上 1 的个数是 $d+1$ 的倍数
3. 组合计数：用数位 DP 或生成函数计算满足条件的布局数
4. 模运算：结果对 $10^9+7$ 取模

通过将博弈论与组合数学结合，可以求出所有先手必胜的初始局面数量。