QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[+1]
Statistics

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={a1,a2,,aN} of the integers 1N, where N300. 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 di(a) denote the depth of node i in the tree corresponding to a, meaning the number of nodes on the path from ai to the root. In the above example, d4(a)=1,d2(a)=d5(a)=2, and d1(a)=d3(a)=3.

The number of inversions of a is equal to the number of pairs of integers (i,j) such that 1i<jN and ai>aj. The cows know that the a that FJ will use to generate the BST has exactly K inversions (0KN(N1)2). Over all a satisfying this condition, compute the remainder when adi(a) is divided by M for each 1iN.

Input Format

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 [108,109+9].

Output Format

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 1

3 0 192603497

Sample Output 1

1 2 3

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

Sample Input 2

3 1 144408983

Sample Output 2

3 4 4

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

Problem credits: Yinzhan Xu