8066: USACO 2019 December Contest, Platinum —— Problem 3. Tree Depth
[Creator : ]
Description
For the new year, Farmer John decided to give his cows a festive binary search tree (BST)! To generate the BST, FJ starts with a permutation $a=\{a_1,a_2,…,a_N\}$ of the integers 1…N, where N≤300. He then runs the following pseudocode with arguments 1 and N.
For example, the permutation {3,2,5,1,4} generates the following BST:
Let $d_i(a)$ denote the depth of node i in the tree corresponding to a, meaning the number of nodes on the path from $a_i$ to the root. In the above example, $d_4(a)=1,d_2(a)=d_5(a)=2$, and $d_1(a)=d_3(a)=3$.
The number of inversions of a is equal to the number of pairs of integers (i,j) such that 1≤i<j≤N and $a_i>a_j$. The cows know that the a that FJ will use to generate the BST has exactly K inversions ($0≤K≤\frac{N(N−1)}{2}$). Over all a satisfying this condition, compute the remainder when $\sum_a d_i(a)$ is divided by M for each 1≤i≤N.
generate(l,r):
if l > r, return empty subtree;
x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
return a BST with x as the root,
generate(l,x-1) as the left subtree,
generate(x+1,r) as the right subtree;
For example, the permutation {3,2,5,1,4} generates the following BST:
4 / \ 2 5 / \ 1 3
Let $d_i(a)$ denote the depth of node i in the tree corresponding to a, meaning the number of nodes on the path from $a_i$ to the root. In the above example, $d_4(a)=1,d_2(a)=d_5(a)=2$, and $d_1(a)=d_3(a)=3$.
The number of inversions of a is equal to the number of pairs of integers (i,j) such that 1≤i<j≤N and $a_i>a_j$. The cows know that the a that FJ will use to generate the BST has exactly K inversions ($0≤K≤\frac{N(N−1)}{2}$). Over all a satisfying this condition, compute the remainder when $\sum_a d_i(a)$ is divided by M for each 1≤i≤N.
Input
The only line of input consists of three space-separated integers N,K, and M, followed by a new line. M will be a prime number in the range $[10^8,10^9+9]$.
Output
Print N space-separated integers denoting $\sum_a d_i(a)\ (\bmod M)$ for each 1≤i≤N.
Sample 1 Input
3 0 192603497
Sample 1 Output
1 2 3
Here, the only permutation is a={1,2,3}.
Sample 2 Input
3 1 144408983
Sample 2 Output
3 4 4
Here, the two permutations are a={1,3,2} and a={2,1,3}.