#PU974. USACO 2019 December Contest, Platinum — Problem 3. Tree Depth
USACO 2019 December Contest, Platinum — Problem 3. Tree Depth
USACO 2019 December Contest, Platinum — Problem 3. Tree Depth
题目描述
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
of the integers , where . He then runs the following
pseudocode with arguments and
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 generates the following BST:
4
/
2 5
/ \
1 3
Let denote the depth of node in the tree corresponding to
meaning the number of nodes on the path from to the root. In the above
example, and
The number of inversions of is equal to the number of pairs of integers
such that and The cows know that the that
FJ will use to generate the BST has exactly inversions
. Over all satisfying this condition, compute
the remainder when is divided by for each
输入格式
The only line of input consists of three space-separated integers and , followed by a new line. will be a prime number in the range
输出格式
Print space-separated integers denoting for each BATCHING: Test cases 3-4 satisfy Test cases 5-7 satisfy Test cases 8-10 satisfy
数据范围
(见题面原文)
样例
样例 1
3 0 192603497
1 2 3
Here, the only permutation is $a=\{1,2,3\}.$
样例 2
3 1 144408983
3 4 4
Here, the two permutations are $a=\{1,3,2\}$ and $a=\{2,1,3\}.$
Problem credits: Yinzhan Xu