CF2001E2 Deterministic Heap (Hard Version)

这是该问题的难度较高版本。两种版本的区别在于确定性最大堆的定义、时间限制以及 $n$ 和 $t$ 的约束。只有当你同时解决了两个版本的问题时，才能进行 hack。 考虑一棵大小为 $2^n - 1$ 的完美二叉树，节点编号从 $1$ 到 $2^n-1$，根节点为 $1$。对于每个顶点 $v$（$1 \le v \le 2^{n - 1} - 1$），顶点 $2v$ 是其左儿子，顶点 $2v + 1$ 是其右儿子。每个节点 $v$ 还被赋予一个值 $a_v$。 定义操作 $\mathrm{pop}$ 如下： 1. 初始化变量 $v$ 为 $1$； 2. 重复以下过程，直到顶点 $v$ 是叶子节点（即 $2^{n - 1} \le v \le 2^n - 1$）： 1. 在 $v$ 的两个子节点中，选择值较大的那个，记为 $x$；如果它们的值相等（即 $a_{2v} = a_{2v + 1}$），可以任选其一； 2. 将 $a_x$ 赋值给 $a_v$（即 $a_v := a_x$）； 3. 将 $x$ 赋值给 $v$（即 $v := x$）； 3. 将 $a_v$ 赋值为 $-1$（即 $a_v := -1$）。 当且仅当上述操作的每一步选择都是唯一的，即任意时刻 $a_{2v} \neq a_{2v + 1}$，我们称 $\mathrm{pop}$ 操作是确定性的。 如果对于每个顶点 $v$（$1 \le v \le 2^{n - 1} - 1$），都有 $a_v \ge a_{2v}$ 且 $a_v \ge a_{2v + 1}$，则称该二叉树为最大堆（max-heap）。 如果对该堆执行第一次和第二次 $\mathrm{pop}$ 操作时，$\mathrm{pop}$ 操作都是确定性的，则称该最大堆为确定性最大堆。 初始时，每个顶点 $v$ 的 $a_v := 0$（$1 \le v \le 2^n - 1$），你的目标是统计通过恰好执行 $k$ 次如下操作 $\mathrm{add}$ 后，能得到多少种不同的确定性最大堆： - 选择一个整数 $v$（$1 \le v \le 2^n - 1$），对于从 $1$ 到 $v$ 的路径上的每个顶点 $x$，将 $a_x$ 加 $1$。 如果存在某个节点在两个堆中的值不同，则认为这两个堆是不同的。 由于答案可能很大，请输出对 $p$ 取模后的结果。

每个测试点包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 50$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含三个整数 $n, k, p$（$2 \le n \le 100$，$1 \le k \le 500$，$10^8 \le p \le 10^9$，$p$ 为质数）。 保证所有测试数据中 $n$ 的和不超过 $100$，所有测试数据中 $k$ 的和不超过 $500$。

对于每组测试数据，输出一行一个整数，表示通过上述操作恰好得到 $k$ 次后，不同的确定性最大堆的数量，对 $p$ 取模。

对于第一个测试点，如果选择 $v = 1$ 并执行操作，则 $a = [1, 0, 0]$，由于 $a_2 = a_3$，在第一次 $\mathrm{pop}$ 操作时可以任选其一，因此该堆不是确定性最大堆。 如果选择 $v = 2$，则 $a = [1, 1, 0]$，第一次 $\mathrm{pop}$ 操作过程如下： - 初始化 $v$ 为 $1$； - 由于 $a_{2v} > a_{2v + 1}$，选择 $2v$ 作为 $x$，此时 $x = 2$； - 将 $a_x$ 赋值给 $a_v$，此时 $a = [1, 1, 0]$； - 将 $x$ 赋值给 $v$，此时 $v = 2$； - $v$ 为叶子节点，将 $a_v$ 赋值为 $-1$，此时 $a = [1, -1, 0]$。 第二次 $\mathrm{pop}$ 操作过程如下： - 初始化 $v$ 为 $1$； - 由于 $a_{2v} < a_{2v + 1}$，选择 $2v + 1$ 作为 $x$，此时 $x = 3$； - 将 $a_x$ 赋值给 $a_v$，此时 $a = [0, -1, 0]$； - 将 $x$ 赋值给 $v$，此时 $v = 3$； - $v$ 为叶子节点，将 $a_v$ 赋值为 $-1$，此时 $a = [0, -1, -1]$。 由于第一次和第二次 $\mathrm{pop}$ 操作都是确定性的，因此该堆是确定性最大堆。同理，如果选择 $v = 3$，$a$ 也会是确定性最大堆，所以答案为 $2$。 由 ChatGPT 4.1 翻译