Codeforces Round 967 (Div. 2) |
---|
Finished |
This is the hard 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 and the second 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 50$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n, k, p$$$ ($$$2 \le n \le 100$$$, $$$1 \le k \le 500$$$, $$$10^8 \le p \le 10^9$$$, $$$p$$$ is a prime).
It is guaranteed that the sum of $$$n$$$ does not exceed $$$100$$$ 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$$$.
62 1 9982443533 2 9982448533 3 9982443533 4 1000000374 2 1000000394 3 100000037
2 12 40 100 32 224
1100 500 100000037
66681128
287 63 10000003713 437 100000039
83566569 54517140
For the first 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:
And during the second $$$\mathrm{pop}$$$, the following would happen:
Since both the first and the second $$$\mathrm{pop}$$$ operation are 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 |
---|