题意理解

在 $1 \times n$ 的棋盘上放 $m$ 枚金币（每格最多一枚），Alice 和 Bob 轮流操作：

• 每次选一枚金币向左移动至少一格
• 不能移出棋盘，不能越过其他金币
• 无法操作者输

问有多少种初始金币布局（位置）使得 Alice 必胜。

---

核心难点

1. 这是一个博弈问题，需要找到必胜局面
2. $n$ 最大 $150000$，$m$ 最大 $50$，需要高效算法
3. 状态数量巨大，不能直接枚举

---

关键思路：转化为阶梯 Nim 游戏

模型转化

把 $m$ 枚金币的位置排序：$a_1 < a_2 < \cdots < a_m$

将棋盘看作 $m+1$ 段空隙：

• 第 $1$ 段：最左边到第 $1$ 枚金币，长度 $a_1 - 1$
• 第 $i$ 段：第 $i-1$ 枚到第 $i$ 枚金币，长度 $a_i - a_{i-1} - 1$
• 第 $m+1$ 段：第 $m$ 枚金币到最右边，长度 $n - a_m$

---

阶梯 Nim 结论

这个游戏等价于阶梯 Nim，其中：

• 从右往左数，第 $i$ 段空隙对应阶梯的第 $i$ 层
• 移动第 $j$ 枚金币相当于取走第 $j$ 层的一些石子放到第 $j-1$ 层

阶梯 Nim 的结论：只考虑奇数层（从右往左数第 1, 3, 5... 层）的石子数，做 Nim 和（异或和），如果异或和不为 $0$ 则先手必胜。

---

问题转化

设 $b_i$ 表示从右往左数第 $i$ 段空隙的长度：

• $b_1 = n - a_m$
• $b_2 = a_m - a_{m-1} - 1$
• $b_3 = a_{m-1} - a_{m-2} - 1$
• ...
• $b_m = a_2 - a_1 - 1$
• $b_{m+1} = a_1 - 1$

那么先手必胜的条件是：

$$b_1 \oplus b_3 \oplus b_5 \oplus \cdots \neq 0$$

---

计数问题

我们需要计算满足以下条件的 $(a_1, a_2, ..., a_m)$ 个数（$1 \le a_1 < a_2 < \cdots < a_m \le n$）：

• 设 $b_1 = n - a_m$, $b_3 = a_{m-1} - a_{m-2} - 1$, $b_5 = a_{m-3} - a_{m-4} - 1$, ...
• 这些奇数层的 $b$ 的异或和不为 $0$

---

动态规划解法

状态定义

设 $dp[i][j]$ 表示考虑前 $i$ 个二进制位，当前异或和为 $j$ 的方案数。

但这样状态太大，需要优化。

---

关键观察

由于 $m \le 50$，奇数层最多 $\lceil \frac{m+1}{2} \rceil \le 26$ 个。

设奇数层数量为 $k = \lceil \frac{m+1}{2} \rceil$。

我们枚举每个二进制位，用数位 DP 的思想。

---

数位 DP 设计

从高到低考虑二进制位，设 $f[i][j]$ 表示考虑前 $i$ 个高位，当前有多少个奇数层还需要“借位”到低位。

具体来说：

• 我们同时决定所有奇数层在当前位的值（0 或 1）
• 要满足所有空隙长度非负的约束
• 用类似背包的方式转移

---

另一种更直观的方法：容斥

总方案数 = $\binom{n}{m}$

我们计算异或和为 0 的方案数，然后用总方案数减去。

计算异或和为 0 的方案数可以用生成函数：

设 $F(x) = \prod_{i=1}^k (1 + x^{2^i} + x^{2^{i+1}} + \cdots)$ 的某种形式，但需要处理长度限制。

---

实际高效做法

设 $dp[i][mask]$ 表示考虑前 $i$ 位，当前位的进位状态为 $mask$ 的方案数。

这里 $mask$ 表示每个奇数层在当前位是否向高位进位。

由于 $k \le 26$，但 $2^{26}$ 太大，需要优化。

---

最终算法框架

1. 预处理组合数 $\binom{n}{m}$ 用于总方案数
2. 数位 DP：
   • 状态：$f[pos][carry]$，$pos$ 是当前二进制位，$carry$ 是进位状态（压缩）
   • 转移：枚举当前位每个奇数层的取值（0/1），计算新的进位状态
   • 使用滚动数组优化空间
3. 答案计算：
   • 必败方案数 = $f[0][0]$（从高位处理到低位后的状态）
   • 必胜方案数 = $\binom{n}{m} - f[0][0]$

---

复杂度分析

• 状态数：$O(\log n \times 2^k)$，其中 $k = \lceil \frac{m+1}{2} \rceil \le 26$
• 但 $2^{26}$ 太大，实际需要优化状态（很多进位状态不可能出现）
• 可以用 meet-in-middle 或状态剪枝

---

关键代码思路（伪代码）

int k = (m + 2) / 2; // 奇数层数量
vector<dp> f(1 << k, 0);
f[0] = 1;

for (int bit = 60; bit >= 0; bit--) { // 从高位到低位
    vector<dp> new_f(1 << k, 0);
    for (int mask = 0; mask < (1 << k); mask++) {
        if (f[mask] == 0) continue;
        for (int choose = 0; choose < (1 << k); choose++) {
            // 检查选择是否合法
            // 更新新的进位状态
            // 累加到 new_f
        }
    }
    f = new_f;
}

ll lose = f[0]; // 异或和为0的方案数
ll total = C(n, m); // 总方案数
ll win = (total - lose + MOD) % MOD;

---

总结

这道题的核心转化：

1. 将金币移动游戏转化为阶梯 Nim
2. 只关心奇数层空隙长度的异或和
3. 用数位 DP 统计异或和为 0 的方案数
4. 利用 $m$ 小的特点进行状态压缩

这样就能在 $n$ 很大时高效求解。