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:

    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 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.\)

Problem credits: Yinzhan Xu

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

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].\)

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

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Platinum