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

Числа Каталана c_n задаются рекуррентным соотношением:

с₀ = 1,

с_n = , n > 0

Вычислите n-ое число Каталана по модулю m.

Вход. Два целых числа n (0 ≤ n ≤ 10⁴) и m (0 < m ≤ 10⁹).

Выход. Выведите значение c_n mod m.

Пример входа	Пример выхода
5 100	42

РЕШЕНИЕ

числа Каталана

Анализ алгоритма

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

с₀ = 1,

с_n = c₀c_n-1 + c₁c_n-2 + c₂c_n-3 + ... + c_n-1c₀, при n > 0

Например,

· с₀ = 1

· с₁ = c₀c₀ = 1,

· с₂ = c₀c₁ + c₁c₀ = 1 + 1 = 2,

· с₃ = c₀c₂ + c₁c₁ + c₂c₀ = 2 + 1 + 2 = 5,

· с₄ = c₀c₃ + c₁c₂ + c₂c₁ + c₃c₀ = 5 + 2 + 2 + 5 = 14,

· с₅ = c₀c₄ + c₁c₃ + c₂c₂ + c₃c₁ + c₄c₀ = 14 + 5 + 4 + 5 + 14 = 42

Поскольку значение с_n пересчитывается через все предыдущие значения c₀, c₁, c₂, ..., c_n-1, то значения чисел Каталана будем запоминать в линейном массиве.

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

Объявим массив cat, в котором будем запоминать числа Каталана: 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())

В списке cat будем запоминать числа Каталана: 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])