1. 问题回顾

我们有一棵大小为 $2^n - 1$ 的完美二叉树。
初始 $a_v = 0$。
执行 $k$ 次 add 操作：每次选一个节点 $v$，将根到 $v$ 路径上所有节点的值 $+1$。
等价于：最终 $a_u = \sum_{v \in \text{subtree}(u)} c_v$，其中 $c_v$ 是节点 $v$ 被选为 add 目标的次数，
满足 $\sum_v c_v = k$，$c_v \ge 0$ 整数。

题目要求：最终形成的堆是一个 deterministic max-heap，即：

• 满足 max-heap 条件（自动成立，前面已证）；
• 第一次 pop 操作 deterministic（每次比较子节点值不相等）；
• 第二次 pop 操作 deterministic（在第一次 pop 改变树之后，再次比较子节点值不相等）。

我们要数不同的最终 $a$ 数组个数（即不同的 $c$ 分布），模素数 $p$。

---

2. 关键转化（标准解法思路）

已知结论（见原题解）：
第一次 pop 的路径 $P_1$ 和第二次 pop 的路径 $P_2$ 必须是 从根到叶子的两条路径（可能相同），且满足：

1. 对 $P_1$ 上每个内部节点 $u$，第一次 pop 前 $a_{2u} \neq a_{2u+1}$；
2. 对 $P_2$ 上每个内部节点 $w$，第一次 pop 后 $a'_{2w} \neq a'_{2w+1}$。

---

记 $b_u = a_{2u} - a_{2u+1}$。
第一次 pop 的过程等价于：从根开始，每次选择子节点中值较大的方向（由 $b_u$ 的符号决定，若 $b_u > 0$ 则去左孩子，$b_u < 0$ 则去右孩子），一直走到叶子。
所以 $P_1$ 由每个节点上的 $b_u$ 符号唯一确定（不允许 $b_u = 0$）。

第一次 pop 后，$a$ 更新：
设 $P_1 = (u_0, u_1, \dots, u_h)$，其中 $u_0 = 1$，$u_h$ 是叶子。
新值 $a'_{u_i} = a_{u_{i+1}}$（$i = 0..h-1$），$a'_{u_h} = -1$，其余节点 $a'_v = a_v$。

于是第二次 pop 时，我们需要新的 $b'_w = a'_{2w} - a'_{2w+1}$ 对 $P_2$ 上的 $w$ 都不为 0。

---

3. 用 $c$ 表示 $b_u$ 和 $b'_u$

原树中：
$b_u = \sum_{v \in \text{subtree}(2u)} c_v - \sum_{v \in \text{subtree}(2u+1)} c_v$。

第一次 pop 后，对不在 $P_1$ 上的节点 $w$，$b'_w = b_w$ 不变。
对在 $P_1$ 上的节点 $u_i$（$i < h$）：

• 它的左孩子可能是 $u_{i+1}$ 或右孩子是 $u_{i+1}$，取决于 $b_{u_i}$ 的正负；
• 第一次 pop 会把 $a_{u_i}$ 变成 $a_{u_{i+1}}$，这会影响 $b'_{parent(u_i)}$（即 $b'_{u_{i-1}}$），因为 $b_{u_{i-1}}$ 的表达式中有 $a_{u_i}$ 的项（来自 $a_{2\cdot u_{i-1}}$ 或 $a_{2\cdot u_{i-1}+1}$）。

经过仔细推导（可参考 CF 原题解），$b'_u$ 可以写成 $c$ 的线性组合，且当 $u$ 在 $P_2$ 上时，要求 $b'_u \neq 0$，这变成对 $c$ 在 $P_1 \cup P_2$ 上的线性不等式的约束。

---

4. 计数等价问题

事实上，最终化简为：

• 选两条根到叶子的路径 $P_1, P_2$（可能相同）；
• 分配 $c_v \ge 0$，$\sum c_v = k$，使得：
  • 对 $P_1$ 上每个非叶节点 $u$，$b_u \neq 0$；
  • 对 $P_2$ 上每个非叶节点 $w$，$b'_w \neq 0$；
• 不同 $c$ 分布给出不同 $a$（因为 $a_u = \text{subtree sum of } c$ 是单射）。

并且已知结论：对固定的 $P_1, P_2$，满足条件的 $c$ 分配方案数只依赖于 $P_1$ 和 $P_2$ 的 形状（即两条路径的交、差结构），以及 $n$ 和 $k$。

---

5. 树的结构与对称性

由于二叉树是完全且对称的，所有根到叶子的路径在组合计数上等价，除了 $P_1$ 与 $P_2$ 的相对位置。

可以证明：$P_1$ 和 $P_2$ 的关系仅由它们的 最近公共祖先 (LCA) 的深度 $d$ 决定（$d = 0$ 表示根，$d = n-1$ 表示叶子）。
此外，$P_1$ 和 $P_2$ 在 LCA 以下的走向（左或右）不影响计数，只影响 $b_u$ 的符号，而符号由 $c$ 分配决定，但总方案数相同。

所以我们可以按 LCA 的深度 分类。

---

6. DP 状态设计（对应代码）

代码中的 DP 定义：

• dp[j]：处理到当前深度时，对于一条路径 $P_1$（当前已经处理了根到当前深度的节点），该路径上的 $c$ 之和为 $j$ 的方案数（这里的“方案”是指在这个深度以下的子树分配 $c$，使得已处理的 $P_1$ 部分满足 $b \neq 0$ 条件）。
• dp2[l][r]：$P_1$ 的 $c$ 和为 $l$，$P_2$ 的 $c$ 和为 $r$ 的方案数（这里 $l,r$ 是两条路径各自已分配的 $c$ 和，不包括 LCA 以上的部分）。

每次向下扩展一层时：

• 新节点 $u$ 有两个孩子，$P_1$ 会走向其中一个孩子（由 $b_u$ 的正负决定），$P_2$ 也会走向某个孩子（可能不同）。
• 两个孩子子树是独立的，$c$ 分配独立。
• 组合数来自：将 $x$ 个 add 操作分配到 $2^i$ 个节点（$i$ 是当前深度，$2^i$ 个可能的新起点）的方法数。

---

7. 组合数推导（对应 binom 和 binom2）

当我们在深度 $i$（根深度 0）时，考虑将 $x$ 次 add 操作分配到当前子树的某些节点上，这些节点在子树中的位置由路径 $P_1$ 和 $P_2$ 决定。

实际上，标程中的 binom[x] 计算的是：把 $x$ 个不可区分的 add 操作分配到 $m = 2^i$ 个节点（这些节点是当前深度下，某个子树的根集合），允许重复（每个节点可以分配任意次）。
分配方案数 = $\binom{x + m - 1}{m - 1} = \binom{x + m - 1}{x}$。

因为 $m = 2^i$，所以 binom[x] = C(x + 2^i - 1, x) 对 $p$ 取模。
代码中 binom[0]=1，递推：

binom[j] = binom[j-1] * (pow2[i] + j - 2 + p) % p

这是因为 $\binom{x+m-1}{x} = \binom{x+m-2}{x-1} \cdot \frac{x+m-1}{x}$，分母 $x$ 用阶乘逆元处理，分子是 $(m-1+1)(m-1+2)\dots$ 的乘积。
最后乘以 faci[x] 即 $1/x!$。

---

binom2 类似，但 $m = 2^{i+1}$（因为可能涉及两个深度的组合）。

---

8. 转移方程解释

第一部分（处理 $P_1$ 延伸）

for (int j = 0; j <= k; j++)
  for (int x = 0; x < j && j + x <= k; x++)
    nxt[j + x] = (nxt[j + x] + dp[j] * binom[x]) % p;

• dp[j]：当前路径 $P_1$ 已有的 $c$ 和 = $j$。
• 我们选择 $P_1$ 下一步走向左孩子（由 $b_u>0$ 决定），并在这个孩子的子树中分配 $x$ 个 add 操作（这些操作影响 $b_u$ 不为 0，因为左子树和大于右子树和的条件可以通过 $c$ 分配实现）。
• 实际上，$x$ 表示在当前节点 $u$ 的右子树中分配的操作数，但这是代码中的简化，具体推导需结合 $b_u \neq 0$ 条件化为：左子树和 - 右子树和 $\neq 0$，通过给右子树分配 $x$ 个操作（$x$ 从 0 到 $j-1$），可以保证 $b_u \neq 0$。
• 分配 $x$ 到右子树的 $2^i$ 个节点（该深度的右子树根集合）的方式数 = binom[x]。

然后 nxt 再做前缀和（for (int j=1; j<=k; j++) nxt[j] = (nxt[j-1] + nxt[j]) % p），这是为了与 $P_2$ 部分合并做准备。

---

第二部分（合并 $P_1$ 和 $P_2$ 的转移）

nxt2 的更新分两块：

第一块：$P_1$ 和 $P_2$ 在当前节点 $u$ 分叉（即 $P_2$ 走向与 $P_1$ 不同的孩子）。
tmp[l][r] 记录 $P_1$ 的 $c$ 和 = $l$，$P_2$ 的 $c$ 和 = $r$ 的方案数（这里 $l,r$ 不包含当前节点）。
枚举 $l$（来自 dp[l]）和 $r$（来自 binom[r] 分配给与 $P_1$ 不同的分支）。
最后用 nxt[r] 乘上去（nxt[r] 已经包含了 $P_1$ 在前缀中的可能性）。

第二块：$P_1$ 和 $P_2$ 在当前节点 $u$ 走同一个孩子（即 $P_1=P_2$ 到目前为止）。
这时 dp2[l][r] 表示两条路径已有的 $c$ 和分别为 $l$ 和 $r$（$l \ge r$ 因为 $P_1$ 和 $P_2$ 重合部分一致，但 $l$ 可能大于 $r$ 因为 $P_2$ 可能短一些？不，这里是两条路径各自的和，不是差）。
然后枚举它们共同走向一个孩子，分配 $r$ 到该孩子的子树（binom2[r]）。

---

9. 最终答案

最后 dp2[l][r] 表示：处理完所有深度后，$P_1$ 的 $c$ 和 = $l$，$P_2$ 的 $c$ 和 = $r$ 的方案数，且 $l+r \le k$。
总方案数 = $\sum_{l=0}^k \sum_{r=0}^{k-l} dp2[l][r]$。

再乘上 $2^{n-1}$：为什么？因为最后一步 $P_1$ 和 $P_2$ 走到叶子时，最后一步的选择（叶子是左还是右）不会影响 $b$ 条件（叶子无子节点），但不同的叶子选择产生不同的 $a$ 分布，并且所有对称的叶子分配数 = 叶子数 = $2^{n-1}$。所以总 deterministic max-heap 数 = （$\sum dp2$）$\times 2^{n-1}$。

---

10. 复杂度

$O(n \cdot k^3)$ 理论上，但代码通过前缀和优化到 $O(n \cdot k^2)$，对于 $k \le 500$ 可行。

---

11. 总结

该标程实现了一个 DP，在树上按深度递推，枚举两条路径 $P_1, P_2$ 的 $c$ 和分配，利用组合数 $\binom{x + m - 1}{x}$ 分配操作到 $m$ 个节点，最终统计满足 deterministic pop 条件的 $c$ 分布数，并乘以叶子选择数 $2^{n-1}$ 得到答案。