## USACO 2019 December Contest, Platinum

## Problem 3. Tree Depth

Contest has ended.

**Log in to allow submissions in analysis mode**

To generate the BST, FJ starts with a permutation $a=\{a_1,a_2,\ldots,a_N\}$ of the integers $1\ldots N$, where $N\le 300$. He then runs the following pseudocode with arguments $1$ and $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\le i<j\le 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\le K\le \frac{N(N-1)}{2})$. Over all $a$ satisfying this condition, compute the remainder when $\sum_ad_i(a)$ is divided by $M$ for each $1\le i\le N.$

#### INPUT FORMAT (file treedepth.in):

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 FORMAT (file treedepth.out):

Print $N$ space-separated integers denoting $\sum_ad_i(a)\pmod{M}$ for each $1\le i\le N.$#### BATCHING:

- Test cases 3-4 satisfy $N\le 8.$
- Test cases 5-7 satisfy $N\le 20.$
- Test cases 8-10 satisfy $N\le 50.$

#### SAMPLE INPUT:

3 0 192603497

#### SAMPLE OUTPUT:

1 2 3

Here, the only permutation is $a=\{1,2,3\}.$

#### SAMPLE INPUT:

3 1 144408983

#### SAMPLE OUTPUT:

3 4 4

Here, the two permutations are $a=\{1,3,2\}$ and $a=\{2,1,3\}.$

Problem credits: Yinzhan Xu