← 返回题目列表

Codeforces · 2001/E1

E1. 确定性堆(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。两个版本之间的区别在于确定性最大堆的定义、时间限制以及对 $$$n$$$ 和 $$$t$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

考虑一棵大小为 $$$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$$$); 在 $$$v$$$ 的子节点中,选择值较大的一个,并将该顶点表示为 $$$x$$$;如果它们的值相等(即 $$$a_{2v} = a_{2v + 1}$$$),则可以选择其中任何一个; 将 $$$a_x$$$ 分配给 $$$a_v$$$ (即 $$$a_v := a_x$$$); 将 $$$x$$$ 分配给 $$$v$$$ (即 $$$v := x$$$);
3. 将 $$$-1$$$ 分配给 $$$a_v$$$ (即 $$$a_v := -1$$$)。

如果存在唯一的方法来执行 $$$\mathrm{pop}$$$ 操作,那么我们就说 $$$\mathrm{pop}$$$ 操作是确定性的。换句话说,只要在它们之间进行选择,$$$a_{2v} \neq a_{2v + 1}$$$ 就会成立。

如果对于每个顶点 $$$v$$$ ($$$1 \le v \le 2^{n - 1} - 1$$$),$$$a_v \ge a_{2v}$$$ 和 $$$a_v \ge a_{2v + 1}$$$ 都成立,则二叉树称为最大堆。

如果我们第一次执行 $$$\mathrm{pop}$$$ 操作对于堆来说是确定性的,则最大堆是确定性的。

最初,$$$a_v := 0$$$ 对于每个顶点 $$$v$$$ ($$$1 \le v \le 2^n - 1$$$),你的目标是计算通过应用以下操作 $$$\mathrm{add}$$$ 精确 $$$k$$$ 次产生的不同确定性最大堆的数量:

- 选择一个整数 $$$v$$$ ($$$1 \le v \le 2^n - 1$$$),并且对于 $$$1$$$ 和 $$$v$$$ 之间路径上的每个顶点 $$$x$$$,将 $$$1$$$ 添加到 $$$a_x$$$。

如果堆中存在一个具有不同值的节点,则认为两个堆不同。

由于答案可能很大,因此以 $$$p$$$ 为模打印它。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n, k, p$$$ ($$$1 \le n, k \le 500$$$, $$$10^8 \le p \le 10^9$$$, $$$p$$$ 是质数)。

保证所有测试用例的 $$$n$$$ 总和与 $$$k$$$ 总和不超过 $$$500$$$。

输出

对于每个测试用例,输出一行包含一个整数:通过应用上述操作 $$$\mathrm{add}$$$ 恰好 $$$k$$$ 次产生的不同确定性最大堆的数量,以 $$$p$$$ 为模。

示例

输入 #1

7
1 13 998244353
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037

输出 #1

1
2
12
52
124
32
304

输入 #2

1
500 500 100000007

输出 #2

76297230

输入 #3

6
87 63 100000037
77 77 100000039
100 200 998244353
200 100 998244353
32 59 998244853
1 1 998244353

输出 #3

26831232
94573603
37147649
847564946
727060898
1

注意

对于第一个测试用例,只有一种方法可以生成$$$a$$$,并且这样的序列是确定性最大堆,所以答案是$$$1$$$。

对于第二个测试用例,如果我们选择 $$$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$$$ 是叶子,将 $$$-1$$$ 分配给 $$$a_v$$$,然后 $$$a = [1, -1, 0]$$$

由于第一个 $$$\mathrm{pop}$$$ 操作是确定性的,因此这是一个确定性的最大堆。另外,如果我们选择 $$$v = 3$$$,则 $$$a$$$ 将是确定性最大堆,因此答案是 $$$2$$$。