Числа Каталана#9643

Числа Каталана (Розбір)

Рекурентне співвідношення перепишемо у вигляді:

с_{0} = 1, с_{n} = c_{0} c_{n - 1} + c_{1} c_{n - 2} + c_{2} c_{n - 3} + ... + c_{n - 1} c_{0}, при n > 0

с_0 = 1, \\ с_n = c_0c_{n-1} + c_1c_{n-2} + c_2c_{n-3} + ... + c_{n-1}c_0,~при~n > 0

Наприклад,

$с_{0} = 1$ с_0 = 1
$с_{1} = c_{0} c_{0} = 1$ с_1 = c_0c_0 = 1,
$с_{2} = c_{0} c_{1} + c_{1} c_{0} = 1 + 1 = 2$ с_2 = c_0c_1 + c_1c_0 = 1 + 1 = 2,
$с_{3} = c_{0} c_{2} + c_{1} c_{1} + c_{2} c_{0} = 2 + 1 + 2 = 5$ с_3 = c_0c_2 + c_1c_1 + c_2c_0 = 2 + 1 + 2 = 5,
$с_{4} = c_{0} c_{3} + c_{1} c_{2} + c_{2} c_{1} + c_{3} c_{0} = 5 + 2 + 2 + 5 = 14$ с_4 = c_0c_3 + c_1c_2 + c_2c_1 + c_3c_0 = 5 + 2 + 2 + 5 = 14,
$с_{5} = c_{0} c_{4} + c_{1} c_{3} + c_{2} c_{2} + c_{3} c_{1} + c_{4} c_{0} = 14 + 5 + 4 + 5 + 14 = 42$ с_5 = c_0c_4 + c_1c_3 + c_2c_2 + c_3c_1 + c_4c_0 = 14 + 5 + 4 + 5 + 14 = 42

Оскільки значення $с_{n}$ с_n обчислюється на основі всіх попередніх значень $c_{0}, c_{1}, c_{2}, ..., c_{n - 1}$ c_0, c_1, c_2, ..., c_{n-1}, будемо зберігати числа Каталана в лінійному масиві.

Реалізація алгоритму

Оголосимо масив $c a t$ , в якому будемо зберігати значення чисел Каталана: $c a t [i] = c_{i}$ cat[i] = c_i.

long long cat[10001];

Зчитаємо вхідні дані.

scanf("%lld %lld", &n, &m);

Обчислюємо числа Каталана за рекурентною формулою.

cat[0] = 1;
for (i = 1; i <= n; i++)
{
  for (j = 0; j < i; j++)
    cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m;
}

Виводимо $n$ -те число Каталана.

printf("%lld\n", cat[n]);

Python реалізація

Зчитаємо вхідні дані.

n, m = map(int, input().split())

У списку $c a t$ будемо зберігати значення чисел Каталана: $c a t [i] = c_{i}$ cat[i] = c_i.

cat = [0] * (n + 1)

Обчислюємо числа Каталана за рекурентною формулою.

cat[0] = 1
for i in range(1, n + 1):
  for j in range(i):
    cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m

Виводимо $n$ -те число Каталана.

print(cat[n])