Codeforces Round 967 (Div. 2) |
---|
Finished |
This is the easy version of the problem. The difference between the two versions is the definition of deterministic max-heap, time limit, and constraints on $$$n$$$ and $$$t$$$. You can make hacks only if both versions of the problem are solved.
Consider a perfect binary tree with size $$$2^n - 1$$$, with nodes numbered from $$$1$$$ to $$$2^n-1$$$ and rooted at $$$1$$$. For each vertex $$$v$$$ ($$$1 \le v \le 2^{n - 1} - 1$$$), vertex $$$2v$$$ is its left child and vertex $$$2v + 1$$$ is its right child. Each node $$$v$$$ also has a value $$$a_v$$$ assigned to it.
Define the operation $$$\mathrm{pop}$$$ as follows:
Then we say the $$$\mathrm{pop}$$$ operation is deterministic if there is a unique way to do such operation. In other words, $$$a_{2v} \neq a_{2v + 1}$$$ would hold whenever choosing between them.
A binary tree is called a max-heap if for every vertex $$$v$$$ ($$$1 \le v \le 2^{n - 1} - 1$$$), both $$$a_v \ge a_{2v}$$$ and $$$a_v \ge a_{2v + 1}$$$ hold.
A max-heap is deterministic if the $$$\mathrm{pop}$$$ operation is deterministic to the heap when we do it for the first time.
Initially, $$$a_v := 0$$$ for every vertex $$$v$$$ ($$$1 \le v \le 2^n - 1$$$), and your goal is to count the number of different deterministic max-heaps produced by applying the following operation $$$\mathrm{add}$$$ exactly $$$k$$$ times:
Two heaps are considered different if there is a node which has different values in the heaps.
Since the answer might be large, print it modulo $$$p$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n, k, p$$$ ($$$1 \le n, k \le 500$$$, $$$10^8 \le p \le 10^9$$$, $$$p$$$ is a prime).
It is guaranteed that the sum of $$$n$$$ and the sum of $$$k$$$ over all test cases does not exceed $$$500$$$.
For each test case, output a single line containing an integer: the number of different deterministic max-heaps produced by applying the aforementioned operation $$$\mathrm{add}$$$ exactly $$$k$$$ times, modulo $$$p$$$.
71 13 9982443532 1 9982443533 2 9982448533 3 9982443533 4 1000000374 2 1000000394 3 100000037
1 2 12 52 124 32 304
1500 500 100000007
76297230
687 63 10000003777 77 100000039100 200 998244353200 100 99824435332 59 9982448531 1 998244353
26831232 94573603 37147649 847564946 727060898 1
For the first testcase, there is only one way to generate $$$a$$$, and such sequence is a deterministic max-heap, so the answer is $$$1$$$.
For the second testcase, if we choose $$$v = 1$$$ and do the operation, we would have $$$a = [1, 0, 0]$$$, and since $$$a_2 = a_3$$$, we can choose either of them when doing the first $$$\mathrm{pop}$$$ operation, so such heap is not a deterministic max-heap.
And if we choose $$$v = 2$$$, we would have $$$a = [1, 1, 0]$$$, during the first $$$\mathrm{pop}$$$, the following would happen:
Since the first $$$\mathrm{pop}$$$ operation is deterministic, this is a deterministic max-heap. Also, if we choose $$$v = 3$$$, $$$a$$$ would be a deterministic max-heap, so the answer is $$$2$$$.
Name |
---|