Katlana Ədədləri#9643

Katlana Ədədləri (Həll təhlili)

Yenidənqaytarma əlaqəsini aşağıdakı kimi yazaq:

c_{0} = 1, c_{n} = c_{0} c_{n - 1} + c_{1} c_{n - 2} + c_{2} c_{n - 3} + ... + c_{n - 1} c_{0}, n > 0 ik e n

c_0 = 1, \\ c_n = c_0c_{n-1} + c_1c_{n-2} + c_2c_{n-3} + ... + c_{n-1}c_0,~n > 0~iken

Məsələn,

$c_{0} = 1$ c_0 = 1
$c_{1} = c_{0} c_{0} = 1$ c_1 = c_0c_0 = 1,
$c_{2} = c_{0} c_{1} + c_{1} c_{0} = 1 + 1 = 2$ c_2 = c_0c_1 + c_1c_0 = 1 + 1 = 2,
$c_{3} = c_{0} c_{2} + c_{1} c_{1} + c_{2} c_{0} = 2 + 1 + 2 = 5$ c_3 = c_0c_2 + c_1c_1 + c_2c_0 = 2 + 1 + 2 = 5,
$c_{4} = c_{0} c_{3} + c_{1} c_{2} + c_{2} c_{1} + c_{3} c_{0} = 5 + 2 + 2 + 5 = 14$ c_4 = c_0c_3 + c_1c_2 + c_2c_1 + c_3c_0 = 5 + 2 + 2 + 5 = 14,
$c_{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$ c_5 = c_0c_4 + c_1c_3 + c_2c_2 + c_3c_1 + c_4c_0 = 14 + 5 + 4 + 5 + 14 = 42

$c_{n}$ c_n dəyəri əvvəlki bütün $c_{0}, c_{1}, c_{2}, ..., c_{n - 1}$ c_0, c_1, c_2, ..., c_{n-1} dəyərlərinə əsasən hesablandığı üçün, Katalan ədədlərini xətti bir massivdə saxlayacağıq.

Alqoritmin reallaşdırılması

Katalan ədədlərinin dəyərlərini saxlayacağımız $c a t$ massivini elan edəcəyik: $c a t [i] = c_{i}$ cat[i] = c_i.

long long cat[10001];

Giriş məlumatlarını oxuyuruq.

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

Yenidənqaytarma formuluna əsasən Katalan ədədlərini hesablayırıq.

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$ -ci Katalan ədədini çıxışa veririk.

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

Python reallaşdırılması

Giriş məlumatlarını oxuyuruq.

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

Katalan ədədlərinin dəyərlərini saxlayacağımız $c a t$ siyahısını elan edirik: $c a t [i] = c_{i}$ cat[i] = c_i.

cat = [0] * (n + 1)

Yenidənqaytarma formuluna əsasən Katalan ədədlərini hesablayırıq.

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$ -ci Katalan ədədini çıxışa veririk.

print(cat[n])