Tree Depth

题目描述

为了迎接新年，农夫约翰决定送给他的奶牛们一棵喜庆的二叉搜索树（BST）！ 为了生成这棵 BST，FJ 先从整数 $1\ldots N$ 的一个排列 $a=\{a_1,a_2,\ldots,a_N\}$ 开始，其中 $N\le 300$。然后他以参数 $1$ 和 $N$ 运行如下伪代码。 generate(l,r): if l > r, return empty subtree; x = argmin_{l <= i <= r} a_i; // {a_l,...,a_r} 中最小的 a_i 的下标 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$ 的逆序对数量等于满足 $1\le i<j\le N$ 且 $a_i>a_j$ 的整数对 $(i,j)$ 的数量。奶牛们知道，FJ 用于生成 BST 的排列 $a$ 恰好有 $K$ 个逆序对 $(0\le K\le \frac{N(N-1)}{2})$。在所有满足该条件的排列 $a$ 中，对于每个 $1\le i\le N$，计算 $\sum_a d_i(a)$ 除以 $M$ 的余数。

输入格式

输入只有一行，包含三个用空格分隔的整数 $N, K,$ 和 $M$，并以换行结束。$M$ 是一个素数，范围为 $[10^8,10^9+9]$。

输出格式

输出 $N$ 个用空格分隔的整数，表示对于每个 $1\le i\le N$，$\sum_a d_i(a)\pmod{M}$ 的值。

3 0 192603497

1 2 3

3 1 144408983

3 4 4

提示

BATCHING: 测试点 3-4 满足 $N\le 8.$ 测试点 5-7 满足 $N\le 20.$ 测试点 8-10 满足 $N\le 50.$ 这里，唯一的排列是 $a=\{1,2,3\}.$ 这里，这两个排列是 $a=\{1,3,2\}$ 和 $a=\{2,1,3\}.$ 题目鸣谢：Yinzhan Xu

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum