题解 — 「黎明之路」构造计数（详细说明）

问题回顾（简明版）

底层有 (k) 个基石（只含 A 或 B），上层由下层两两合并形成：

相同 → A（记为 0）
不同 → B（记为 1）

把 A/B 映射为 0/1 后，上一层正好是对相邻两位 异或（XOR） 的结果。已知总的 A 个数为 (M)、B 个数为 (N)，并且 (M+N) 恰好是三角数 (\frac{k(k+1)}{2})。求：有多少种长度为 (k) 的底层二进制串，使得整座三角形（从底层到顶层所有格子）中 0 的总数为 (M)、1 的总数为 (N)。

关键观察

等价变换（用 0/1 表示）
- A ↔ 0，B ↔ 1。
- 两个相同得 0，两个不同得 1；这与 x ^ y（异或）恰好一致。
- 所以，一次“上移”操作将长度为 (i) 的二进制串 now 变为长度为 (i-1) 的 now' = (now) xor (now >> 1) 的低 (i-1) 位。
递推唯一确定性 底层确定后，整座三角形所有层都唯一确定（逐层异或得到上一层），因此我们只需枚举底层所有可能，统计整座三角的 0/1 数量，判断是否等于 (M,N)。
位运算加速 用整数的二进制位表示一层（最低位表示第一个位置或按约定表示某一端），有如下变换步骤能快速得到上一层：
```
now ^= (now >> 1);
now &= (1 << (i-1)) - 1;   // 只保留前 i-1 位
```
这可以在 O(1)（按机字位宽）时间内完成一层的转换（实际是按位并行完成），并可用内置的位计数函数（如 C++ 的 bitset::count() 或 __builtin_popcount）快速统计当前层中 1 的数量。

暴力枚举（位运算实现）

算法思路

根据输入 (M,N)，由 (S=M+N) 计算层数 (k)（满足 (k(k+1)/2 = S)，题目保证存在）。
枚举底层所有 (2^k) 个二进制串（对于较小的 (k) 可行）。对于每个 now：
- 令 i = k，循环：
  - 统计 now 中 1 的数量，累加到 num_b（B 的总数），num_a 增加 i - count1；
  - 变换 now 为上一层：now ^= now >> 1; now &= (1 << (i-1)) - 1;；
  - i--，直到 i == 0（所有层统计完）。
- 判断 num_a == M && num_b == N，如果成立计数加 1。

复杂度

时间复杂度：(O(2^k \cdot k))。每个底层枚举需要进行 (k) 次层上移操作，每次操作包含位计数（可以视为 O(1) 于机字位宽，但严格说为 O(k/wordsize)）。
空间复杂度：O(1)。

适用条件：当 (k) 较小时该方法可行。题中示例 (k=3) 或 (k=2) 很适合此法。但若 (k) 很大（例如 1000），暴力枚举不可行。

示例代码（C++ 位运算枚举法）

#include <bits/stdc++.h>
using namespace std;

int m, n;

// 检查底层状态 now（低 k 位有效）是否会在整座三角中产生 m 个 0（A）和 n 个 1（B）
bool check(int now, int k) {
    int num_a = 0, num_b = 0;
    for (int i = k; i >= 1; --i) {
        int cnt1 = __builtin_popcount(now);   // now 中 1 的个数
        num_b += cnt1;
        num_a += (i - cnt1);
        // 变换到上一层
        now ^= (now >> 1);
        if (i - 1 >= 31) { // 若 i 很大，移位需要注意（但本题近用小 i）
            // 若使用 64 位，请替换为 long long 并使用 (1ULL << (i-1)) - 1
        }
        now &= ((1 << (i - 1)) - 1);
    }
    return (num_a == m && num_b == n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    int S = m + n;
    // 求 k 满足 k*(k+1)/2 == S
    int k = (int)(sqrt(2.0 * S));
    // 保险起见可以调整 k 以确保等式成立
    if (k * (k + 1) / 2 != S) {
        cout << 0 << "\n";
        return 0;
    }
    long long ans = 0;
    int limit = 1 << k; // 注意：当 k >= 31 时会溢出，应改为 64 位并判断 k 上界
    for (int mask = 0; mask < limit; ++mask) {
        if (check(mask, k)) ++ans;
    }
    cout << ans << "\n";
    return 0;
}

另一种回溯（DFS）思路（剪枝）

当 (k) 稍大且暴力枚举不可行时，可用 按层构造、并剪枝 的 DFS：

要点

按层从上到下或从底到上逐格填充，但注意填法并不是逐格独立的：填下一层某位置后会决定上面某些位置。
常见做法是自底向上按“行”填：第 1 行（顶）只有 1 个格，第 2 行 2 个格，...，直到第 k 行底层 (k) 个格。因为顶层是由底层的规则累积决定的，逆向填充要遵守与父行的一致性（见题中给出的 DFS 代码）。
在 DFS 过程中维护当前已经剩余的 m（需分配的 0）和 n（需分配的 1），一旦某一步使得 m<0 或 n<0，立即回溯（剪枝）。

该方法常用于 (k) 能到几十但仍需剪枝的场合，且在题目某些约束下能显著减少搜索空间。

题中给出的 DFS 代码实现了按行构建并在构造过程中利用父格决定子格（或反之），是一个有效的搜索策略。

题解 | # ONE PIECE：黎明之路#