---

题意简述

有一棵大小为 $2^n - 1$ 的完美二叉树，节点编号 $1$ 到 $2^n - 1$，根为 $1$，节点 $v$ 的左孩子为 $2v$，右孩子为 $2v + 1$。
初始所有节点值为 $0$。

一次 add 操作：选择节点 $v$，将根节点到 $v$ 路径上的所有节点值加 $1$。
执行恰好 $k$ 次 add 操作后，得到一棵树。要求该树同时满足：

• 最大堆性质：对任意非叶子节点 $v$，有 $a_v \ge a_{2v}$ 且 $a_v \ge a_{2v + 1}$。
• 确定性：第一次执行 pop 操作时，每一步选择的子节点唯一，即对于每个非叶子节点 $v$，必须满足 $a_{2v} \neq a_{2v + 1}$。

问：有多少种不同的最终堆（按节点值区分），结果对给定素数 $p$ 取模。

---

核心转化

1. 子树操作次数模型

一次 add 操作选择节点 $u$，会使得 $u$ 的所有祖先的值加 $1$。
因此，最终节点 $v$ 的值 $a_v$ 等于 以 $v$ 为根的子树中被选中的 add 操作次数。

记 $s(v) = a_v$，则：

• $s(v)$ 是非负整数，表示 $v$ 的子树内的总操作次数。
• 对任意非叶子 $v$，最大堆性质等价于：$$s(v) \ge s(2v), \quad s(v) \ge s(2v + 1)$$
• 确定性条件等价于：$$s(2v) \neq s(2v + 1)$$

并且，所有节点的 $s(v)$ 并非独立，它们满足递推关系：

$$s(v) = \text{self}_v + s(2v) + s(2v + 1)$$

其中 $\text{self}_v$ 是节点 $v$ 自身作为 add 目标被选中的次数。

---

2. 确定性条件的结构

从根开始，$s(2) \neq s(3)$，不妨设 $s(2) > s(3)$，则 pop 走向节点 $2$。
接着 $s(4) \neq s(5)$，依此类推。

因此，存在一条从根到某个叶子的唯一路径，称为 主路径，每一步都走向值较大的子节点，且路径上每个内部节点的两个子节点值严格不等。

设主路径为：

$$p_0 = 1,\; p_1,\; p_2,\; \dots,\; p_{n-1}$$

其中 $p_{n-1}$ 是叶子。
令 $b_i = s(p_i)$，则：

$$b_0 \ge b_1 \ge \dots \ge b_{n-1} \ge 0$$

并且对于每个 $i$（$0 \le i \le n-2$），另一个子节点（不在主路径上）的值严格小于 $b_{i+1}$。

---

3. 非关键子树

对于主路径上的节点 $p_i$，它的另一个子节点称为 旁支根，其子树是一个 非关键子树。
这些非关键子树之间相互独立，且每个非关键子树的根值必须严格小于主路径上对应兄弟节点的值（即 $b_{i+1}$）。

非关键子树内部也必须是确定性最大堆，结构相同但规模更小（高度递减）。

因此，整个结构可以递归描述：

• 主路径将树分割成若干独立的、高度递减的完美二叉树（非关键子树）。
• 每个非关键子树的形式与原问题相同，只是高度更小。

---

动态规划设计

定义状态

设：

$$dp[i][j] = \text{高度为 } i \text{ 的完美二叉树（大小 } 2^i - 1\text{），且该子树内总操作次数为 } j \text{ 的方案数} $$

注意：子树总操作次数等于该子树根节点的值 $s(\text{root})$。

边界条件

高度 $i = 1$ 时，树只有一个节点，总操作次数 $j$ 只能由该节点自身被选中 $j$ 次得到，只有 $1$ 种方案。
因此：

$$dp[1][j] = 1, \quad \forall 0 \le j \le k$$

转移方程

考虑高度 $i+1$ 的树，根为 $R$，左右子树高度为 $i$，根分别为 $L$ 和 $R_c$。
确定性条件要求 $s(L) > s(R_c)$（由对称性，固定左 > 右，最后会通过对称性处理）。

设左子树总操作次数 $j = s(L)$，右子树总操作次数 $x = s(R_c)$，则必须满足 $0 \le x < j$。
根节点 $R$ 的总操作次数 $l = s(R)$ 满足：

$$l = j + x + r, \quad r \ge 0$$

其中 $r$ 是 $R$ 自身被选中的次数。

对于固定的 $j$ 和 $x$：

• 左子树（主路径部分）有 $dp[i][j]$ 种内部方案。
• 右子树（非关键子树）有 $\displaystyle \binom{x + 2^i - 2}{x}$ 种内部方案。
  这是因为右子树有 $2^i - 1$ 个节点，将 $x$ 次不可区分的操作分配到这些节点上（每个节点可被选多次，顺序无关），方案数为 $\binom{x + (2^i - 1) - 1}{x} = \binom{x + 2^i - 2}{x}$。

因此，对于每个 $l \ge j + x$，贡献为 $dp[i][j] \cdot \binom{x + 2^i - 2}{x}$。

在实现中，我们先计算 $nxt[t]$ 表示恰好 $t = j + x$ 时的贡献：

$$nxt[j + x] \mathrel{+}= dp[i][j] \cdot \binom{x + 2^i - 2}{x} $$

然后通过前缀和：

$$dp[i+1][l] = \sum_{t=0}^{l} nxt[t]$$

这样就在 $O(k^2)$ 内完成了从 $i$ 到 $i+1$ 的转移。

组合数预处理

由于 $p$ 是素数，我们可以预处理阶乘 $fac$ 和阶乘逆元 $faci$。
标程中采用了递推方式计算：

$$\text{binom}[x] = \binom{x + 2^i - 2}{x}$$

递推公式：

$$\text{binom}[0] = 1, \quad \text{binom}[x] = \text{binom}[x-1] \cdot \frac{x + 2^i - 2}{x} \pmod p $$

因为：

$$\binom{x + m}{x} = \binom{x-1 + m}{x-1} \cdot \frac{x + m}{x} $$

这里 $m = 2^i - 2$。

---

对称性与最终答案

上述 DP 固定了主路径为“每次走左子节点”的情况。
由于完美二叉树的对称性，以任意叶子作为主路径终点的方案数相同。
叶子共有 $2^{n-1}$ 片，因此最终答案为：

$$\text{ans} = dp[n][k] \times 2^{n-1} \pmod p$$

其中 $dp[n][k]$ 是标程中最后得到的 $dp[k]$。

---

复杂度分析

• 预处理阶乘与逆元：$O(k)$。
• 每个高度 $i$ 计算组合数：$O(k)$。
• 每个高度 $i$ 的转移：枚举 $j$ 和 $x$，$O(k^2)$。
• 总高度 $n \le 500$，$k \le 500$，总复杂度 $O(n k^2) \le 1.25 \times 10^8$，在 3 秒内可通过（C++ 优化）。

---

总结

本题的核心在于：

1. 将堆的值转化为子树操作次数。
2. 利用确定性条件引出主路径与非关键子树结构。
3. 非关键子树的计数归结为组合数。
4. 动态规划自底向上合并，利用前缀和优化。
5. 由对称性乘上叶子数得到最终答案。

标程即实现上述过程。