Độ Sâu Cây

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một hoán vị $a = {a_{1}, a_{2}, \dots, a_{N}}$ của $1, 2, \dots, N$ , ta xây dựng một cây BST như sau:

generate(l, r):
  nếu l > r, trả về cây rỗng;
  x = argmin_{l ≤ i ≤ r} a_i;  // chỉ số của phần tử nhỏ nhất trong a_l..a_r
  trả về BST với x là gốc,
         generate(l, x-1) là cây con trái,
         generate(x+1, r) là cây con phải;

Gọi $d_{i} (a)$ là độ sâu của nút $i$ trong cây tương ứng với $a$ (số nút trên đường từ $a_{i}$ đến gốc). Số nghịch thế của $a$ là số cặp $(i, j)$ với $i < j$ và $a_{i} > a_{j}$ .

Biết rằng $a$ có đúng $K$ nghịch thế, hãy tính $\sum_{a} d_{i} (a) (\mod M)$ với mỗi $1 \leq i \leq N$ , tổng lấy trên tất cả các hoán vị $a$ thỏa mãn điều kiện.

Dữ liệu vào

Một dòng duy nhất gồm ba số nguyên $N$ , $K$ , $M$ .

$1 \leq N \leq 300$
$0 \leq K \leq \frac{N (N - 1)}{2}$
$M$ là số nguyên tố, $10^{8} \leq M \leq 10^{9} + 9$

Dữ liệu ra

In $N$ số nguyên cách nhau bởi dấu cách — giá trị $\sum_{a} d_{i} (a) (\mod M)$ với $i = 1, 2, \dots, N$ .

Ví dụ

Input	Output	Giải thích
3 0 192603497	1 2 3	Hoán vị duy nhất là ${1, 2, 3}$ : BST có gốc 1, con phải 2, cháu phải 3. $d_{1} = 1, d_{2} = 2, d_{3} = 3$ .
3 1 144408983	3 4 4	Hai hoán vị: ${1, 3, 2}$ cho $(d_{1}, d_{2}, d_{3}) = (1, 3, 2)$ ; ${2, 1, 3}$ cho $(2, 1, 2)$ . Tổng: $(3, 4, 4)$ .

Bình luận

Không có bình luận tại thời điểm này.