codeforces#P2001E2. Deterministic Heap (Hard Version)
Deterministic Heap (Hard Version)
Description
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:
- initialize variable $v$ as $1$;
- 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$);
- 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$.
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$.
Input
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
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$.
6
2 1 998244353
3 2 998244853
3 3 998244353
3 4 100000037
4 2 100000039
4 3 100000037
1
100 500 100000037
2
87 63 100000037
13 437 100000039
2
12
40
100
32
224
66681128
83566569
54517140
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$.