3357. [USACO19 Dec Platinum]Tree Depth

【题目描述】

本题面由 @数声风笛 翻译。

对于新的一年，Farmer John 决定给他的母牛放个节日的二叉树（BST）！为了生成BST，Farmer John 以整数$ 1 \cdots N $ $( N ≤ 300 )$的排列$a=\{a_1,a_2,\ldots,a_N\}$开始。然后，他使用参数 $1$ 和 $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;

例如，排列$\{3,2,5,1,4 \} $生成以下BST：

    4
   / \
  2   5
 / \
1   3

令$d_i(a)$表示树中与 $a$ 对应的节点 $i$ 的深度，表示从 $a_i$ 到根的路径上的节点数。在以上示例中，$d_4(a)=1, d_2(a)=d_5(a)=2,$ 并且$d_1(a)=d_3(a)=3.$

$a$ 的逆序对数等于整数对 $(i,j)$ 的数目，从而 $1 ≤ i < j ≤ N$ 且 $a_i > a_j$ 。母牛知道 Farmer John 将用来生成 BST 的 $a$ 恰好具有 $K$ 个逆序对 $(0\le K\le \frac{N(N-1)}{2})$ 。在满足此条件的所有条件下，对于每个 $1 ≤ i ≤ N$ ，计算 $\sum_ad_i(a)$ 除以 $M$ 的余数。

【输入格式】

输入仅有一行，由三个以空格分隔的整数 $N$ ，$K$ 和 $M$ 组成。$M$ 是在 $[10^8,10^9 + 9]$ 范围内的质数。

【输出格式】

一行，包含 $N$ 个数，即对于每个 $1 ≤ i ≤ N$，$\sum_ad_i(a)\pmod{M}$的值。

【样例输入1】

3 0 192603497

【样例输出1】

1 2 3

【样例解释1】

对于该样例，唯一的排列是 $a = \{1,2,3\}$。

【样例输入2】

3 1 144408983

【样例输出2】

3 4 4

【样例解释2】

对于这个样例，满足条件的两个排列分别为 $a=\{1,3,2\}$ 和 $a=\{2,1,3\}$。

【提示】

对于$ 29\% $的测试数据(测试点$ 1\sim4 $)，满足$ N ≤ 8 $。

对于$ 50\% $的测试数据(测试点$ 1\sim7 $)，满足$ N ≤ 20 $。

对于$ 71\% $的测试数据(测试点$ 1\sim10 $)，满足$ N ≤ 50 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月公开赛 Platinum 组