#PU974. USACO 2019 December Contest, Platinum — Problem 3. Tree Depth

    ID: 1278 传统题 文件IO:treedepth 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec19来源:usaco.orgscoring:equal_test_cases数学

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 a={a1,a2,…,aN}a=\{a_1,a_2,\ldots,a_N\} of the integers 1…N1\ldots N, where N≤300N\le 300. He then runs the following pseudocode with arguments 11 and N.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}\{3,2,5,1,4\} generates the following BST: 4 /
2 5 / \ 1 3 Let di(a)d_i(a) denote the depth of node ii in the tree corresponding to a,a, meaning the number of nodes on the path from aia_i to the root. In the above example, d4(a)=1,d2(a)=d5(a)=2,d_4(a)=1, d_2(a)=d_5(a)=2, and d1(a)=d3(a)=3.d_1(a)=d_3(a)=3. The number of inversions of aa is equal to the number of pairs of integers (i,j)(i,j) such that 1≤i<j≤N1\le i<j\le N and ai>aj.a_i>a_j. The cows know that the aa that FJ will use to generate the BST has exactly KK inversions (0≤K≤N(N−1)2)(0\le K\le \frac{N(N-1)}{2}). Over all aa satisfying this condition, compute the remainder when ∑adi(a)\sum_ad_i(a) is divided by MM for each 1≤i≤N.1\le i\le N.

输入格式

The only line of input consists of three space-separated integers N,K,N, K, and MM, followed by a new line. MM will be a prime number in the range [108,109+9].[10^8,10^9+9].

输出格式

Print NN space-separated integers denoting ∑adi(a)(modM)\sum_ad_i(a)\pmod{M} for each 1≤i≤N.1\le i\le N. BATCHING: Test cases 3-4 satisfy N≤8.N\le 8. Test cases 5-7 satisfy N≤20.N\le 20. Test cases 8-10 satisfy N≤50.N\le 50.

数据范围

(见题面原文)

样例

样例 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