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,\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:

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.

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.

Problem credits: Yinzhan Xu

#4131 upload 3회 done 1회 how_to_reg 1명

Tree Depth timer 2초 memory 512MB

#4131

Tree Depth 2초 512MB