Глибина дерева#10295

Глибина дерева

1 секунда

128 мегабайтів

Дуже легка

На Новий рік фермер Джон вирішив подарувати своїм коровам святкове бінарне дерево пошуку (БДП)!

Щоб створити БДП, фермер Джон починає з перестановки $a = {a_{1}, a_{2}, \dots, a_{n}}$ a = \{a_1, a_2, \ldots, a_n\} чисел від $1$ до $n$ , де $n \leq 300$ n \le 300. Потім він виконує наступний псевдокод з аргументами $1$ і $n$ .

generate(l, r):
  if l > r, return пусте піддерево;
  x = argmin_{l <= i <= r} a_i; // індекс min a_i in {a_l, ..., a_r}
  return БДП з x у корені, 
    generate(l, x-1) як ліве піддерево,
    generate(x+1, r) як праве піддерево;

Наприклад, перестановка ${3, 2, 5, 1, 4}$ \{3, 2, 5, 1, 4\} генерує наступне БДП:

Нехай $d_{i} (a)$ d_i(a) позначає глибину вузла $i$ в дереві, що відповідає $a$ , тобто кількість вузлів на шляху від $a_{i}$ a_i до кореня. У наведеному вище прикладі $d_{4} (a) = 1$ d_4(a) = 1, $d_{2} (a) = d_{5} (a) = 2$ d_2(a) = d_5(a) = 2, і $d_{1} (a) = d_{3} (a) = 3$ d_1(a) = d_3(a) = 3.

Кількість інверсій $a$ дорівнює кількості пар цілих чисел $(i, j)$ таких, що $1 \leq i < j \leq n$ 1 \le i < j \le n і $a_{i} > a_{j}$ a_i > a_j. Корови знають, що $a$ , яке фермер Джон буде використовувати для генерації БДП, має рівно $k$ інверсій ( $0 \leq k \leq n \cdot (n - 1) /2$ 0 \le k \le n \cdot (n - 1) / 2). Для всіх $a$ , що задовольняють цій умові, обчислити залишок від ділення $\sum_{a} d_{i} (a)$ \sum_a d_i(a) на $m$ для кожного $1 \leq i \leq n$ 1 \le i \le n.

Вхідні дані

Єдиний рядок містить три цілі числа $n$ , $k$ і $m$ . $m$ є простим числом у діапазоні $[1 0^{8}, 1 0^{9} + 9]$ [10^8, 10^9 + 9].

Вихідні дані

Виведіть $n$ цілих чисел, рівних $\sum_{a} d_{i} (a) (mod m)$ \sum_a d_i(a) \pmod{m} для кожного $1 \leq i \leq n$ 1 \le i \le n.

Приклади

Приклад 1

Приклад 2

Примітка

Приклад 1: єдиною перестановкою буде $a = {1, 2, 3}$ a = \{1, 2, 3\}.

Приклад 2: існують дві перестановки $a = {1, 3, 2}$ a = \{1, 3, 2\} і $a = {2, 1, 3}$ a = \{2, 1, 3\}.