RiseOJ – 트리 깊이

설명

새해를 맞아 농부 존은 소들에게 축제 분위기의 이진 탐색 트리(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; // 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를 생성한다.

$$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$$ 의 반전(inversion)의 개수는 $$1\le i이고 \(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_ad_i(a)$를 $M$으로 나눈 나머지를 계산하여라.$

문제 제공: Yinzhan Xu

제약

배칭

테스트 케이스 3-4는 $N\le 8$ 을 만족한다.
테스트 케이스 5-7은 $N\le 20$ 을 만족한다.
테스트 케이스 8-10은 $N\le 50$ 을 만족한다.

문제 제공: Yinzhan Xu

입력 형식

입력은 한 줄로, 공백으로 구분된 세 정수 $$N, K,$$ $$M$$ 이 주어지고 개행이 뒤따른다. $$M$$ 은 $$[10^8,10^9+9]$$ 범위의 소수이다.

출력 형식

각 $1\le i\le N$ 에 대해 $\sum_ad_i(a)\pmod{M}$ 을 나타내는 $$N$$ 개의 정수를 공백으로 구분하여 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 treedepth.in · 출력을 쓸 파일 treedepth.out

예제 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\}.$

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

트리 깊이

평가 및 의견

풀이 제출