Deterministic Heap (Hard Version)
Contest: Codeforces Round 967 (Div. 2)
Difficulty rating: 2900
Tags: combinatorics, dp, trees

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:

1. initialize variable $$$v$$$ as $$$1$$$;
2. repeat the following process until vertex $$$v$$$ is a leaf (i.e. until $$$2^{n - 1} \le v \le 2^n - 1$$$);   among the children of $$$v$$$, choose the one with the larger value on it and denote such vertex as $$$x$$$; if the values on them are equal (i.e. $$$a_{2v} = a_{2v + 1}$$$), you can choose any of them;  assign $$$a_x$$$ to $$$a_v$$$ (i.e. $$$a_v := a_x$$$);  assign $$$x$$$ to $$$v$$$ (i.e. $$$v := x$$$);
3. assign $$$-1$$$ to $$$a_v$$$ (i.e. $$$a_v := -1$$$).

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:

- Choose an integer $$$v$$$ ($$$1 \le v \le 2^n - 1$$$) and, for every vertex $$$x$$$ on the path between $$$1$$$ and $$$v$$$, add $$$1$$$ to $$$a_x$$$.

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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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:

- initialize $$$v$$$ as $$$1$$$
- since $$$a_{2v} > a_{2v + 1}$$$, choose $$$2v$$$ as $$$x$$$, then $$$x = 2$$$
- assign $$$a_x$$$ to $$$a_v$$$, then $$$a = [1, 1, 0]$$$
- assign $$$x$$$ to $$$v$$$, then $$$v = 2$$$
- since $$$v$$$ is a leaf, assign $$$-1$$$ to $$$a_v$$$, then $$$a = [1, -1, 0]$$$

And during the second $$$\mathrm{pop}$$$, the following would happen:

- initialize $$$v$$$ as $$$1$$$
- since $$$a_{2v} < a_{2v + 1}$$$, choose $$$2v + 1$$$ as $$$x$$$, then $$$x = 3$$$
- assign $$$a_x$$$ to $$$a_v$$$, then $$$a = [0, -1, 0]$$$
- assign $$$x$$$ to $$$v$$$, then $$$v = 3$$$
- since $$$v$$$ is a leaf, assign $$$-1$$$ to $$$a_v$$$, then $$$a = [0, -1, -1]$$$

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$$$.

Example input:
6
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037

Example output:
2
12
40
100
32
224

Example input:
1
100 500 100000037

Example output:
66681128

Editorial:
Make use of symmetry:
For convenience, let $$$\text{det_heap}()$$$ denote # twice-deterministic heap, $$$\text{det_heap}(v)$$$ denote # twice-deterministic heap where the first pop come from leaf $$$v$$$, $$$\text{det_heap}(v, u)$$$ denote # twice-deterministic heap where the first pop come from leaf $$$v$$$, second pop come from leaf $$$u$$$.
Similar to easier version, we have $$$\text{det_heap}() = 2^{n - 1}\cdot\text{det_heap}(2^{n - 1})$$$ because of symmetry.
Then consider enumerate $$$u$$$, the second leaf being popped, we have $$$\text{det_heap}(2^{n - 1}) = \sum\limits_{u = 2^{n - 1} + 1}^{2^n - 1}\text{det_heap}(2^{n - 1}, u)$$$
because of symmetry, again, for any $$$u_1 \neq u_2, LCA(2^{n - 1}, u_1) = LCA(2^{n - 1}, u_2)$$$, we have $$$\text{det_heap}(2^{n - 1}, u_1) = \text{det_heap}(2^{n - 1}, u_2)$$$, so for each LCA, we only need to enumerate leftmost leaf under it as second popped leaf and multiply answer with (# leaves in such subtree).
Rephrase of Problem:
then consider the relation of values between vertices, we have
— picture 1 —
where
• black edge from $$$x$$$ to $$$y$$$ means $$$a_x \le a_y$$$, which comes with nature of $$$\text{add}$$$ operation
• red edge from $$$x$$$ to $$$y$$$ means $$$a_x < a_y$$$, which come from the fact that $$$v$$$ should be first leaf being pulled
• blue edge from $$$x$$$ to $$$y$$$ means $$$a_x < a_y$$$, which come from the fact that $$$u$$$ should be second leaf being pulled
Eliminate Useless Conditions:
Then observe if you have some directed triangle consist of edges $$$(x, y), (y, z), (x, z)$$$, edge $$$(x, z)$$$ didn't bring extra relation so we can delete it, after that, we would have
— picture 2 —
Applying Counting:
Then we can use pair of value of vertices from same depth as the state of dp, and enumerate such pair in increasing order of height while not breaking the relations, then we would have $$$dp[h][l][r]$$$ = # twice-deterministic heap when the left vertex have value l and right vertex have value r and the current height is $$$h$$$.
First, to handle the relation of Z shape formed by red/blue arrows and enumerate value of $$$(L, R, R')$$$, consider the following picture
— picture 3 —
(The red subtree is one-time deterministic heap, while the other can be any heap.)
Also let $$$f(h, k)$$$ denote # deterministic heap for one time pop with height $$$h$$$ after doing operation $$$k$$$ times where the leftmost leaf being pulled, $$$g(h, k)$$$ denote # max heap with height $$$h$$$ after doing operation $$$k$$$ times (We already know how to compute them in easier version of this problem)
Let's fix the value $$$L$$$ and $$$R$$$, and push it to some $$$dp[h][L'][R']$$$, we need to satisfy
• $$$L' > R' > L > R$$$
• $$$L' \ge L + R$$$
in such case, enumerate all pair $$$(L, R), (L > R)$$$ and for all $$$L' \ge L + R, R' \ge L + 1$$$, add $$$f(h - 1, L) \cdot g(h - 1, R)$$$ to $$$dp[h][L'][R']$$$, then for every $$$L' \le R'$$$, eliminate its contribution while for every $$$L' > R'$$$, multiply its contribution with $$$f(h, R') \cdot 2^h$$$. which can be done in $$$O(k^2)$$$.
Second, to handle the relation formed by black/blue edges and enumerate value $$$R'$$$, consider the following picture
— picture 4 —
For each $$$L, R$$$, we need to push it some some $$$dp[h][L'][R']$$$ where the following conditions hold
• $$$L' > R' > L > R$$$
• $$$L' \ge L + R$$$
we can handle it by adding $$$dp[h - 1][L][R]$$$ to $$$dp[L'][R']$$$ for all $$$L' \ge L + R, R' \le L - 1$$$ and for all $$$L' < R'$$$, eliminate its contribution while for the other, multiply the contribution with $$$g(h, R')$$$, which can also be done by prefix sum in $$$O(k^2)$$$.
Then the answer would be $$$2^{n - 1} \cdot \sum\limits_{L + R \le k}dp[h - 2][L][R]$$$ and the problem has been solved in $$$O(nk^2)$$$.