Xoca Nəsrəddin#5101

Xoca Nəsrəddin (Həll təhlili)

Xoca ilə eşşək cədvəlin hansısa $(i, j)$ xanasında görüşürlər. Görüş üsulu üç komponentlə müəyyən olunur: görüş xanası, Xocanın $(1, 1)$ xanasından bu xanaya qədər olan marşrutu və eşşəyin $(n, n)$ xanasından bu xanaya qədər olan marşrutu. Buna görə də hər bir xana üçün Xocanın və eşşəyin həmin xanaya aparan marşrutlarının sayını hesablayırıq.

Tutaq ki, $a [i] [j]$ Xocanın $(1, 1)$ xanasından $(i, j)$ xanasına qədər gedə biləcəyi yolların sayıdır. Xoca yalnız sağa və ya aşağıya hərəkət edir, buna görə də $(i, j)$ xanasına ya onun üstündəki $(i - 1, j)$ (i - 1, j) xanasından, ya da solundakı $(i, j - 1)$ (i, j - 1) xanasından daxil olur:

a [i] [j] = a [i - 1] [j] + a [i] [j - 1], a [1] [1] = 1

a[i][j] = a[i - 1][j] + a[i][j - 1], \\ a[1][1] = 1

Cədvəldən kənar xanalar əlçatmazdır; onlara gedən yolların sayı sıfır hesab olunur.

Eyni qaydada, tutaq ki, $b [i] [j]$ eşşəyin $(n, n)$ xanasından $(i, j)$ xanasına qədər gedə biləcəyi yolların sayıdır. Eşşək yalnız sola və ya yuxarıya hərəkət edir, buna görə də $(i, j)$ xanasına ya onun altındakı $(i + 1, j)$ (i + 1, j) xanasından, ya da sağındakı $(i, j + 1)$ (i, j + 1) xanasından daxil olur:

b [i] [j] = b [i + 1] [j] + b [i] [j + 1], b [n] [n] = 1

b[i][j] = b[i + 1][j] + b[i][j + 1], \\ b[n][n] = 1

Xocanın və eşşəyin marşrutları bir-birindən asılı olmayaraq seçilir. Buna görə də vurma qaydasına əsasən, $(i, j)$ xanasında görüşmə üsullarının sayı $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j]-ə bərabərdir. Müxtəlif xanalarda görüşlər müxtəlif üsullardır, buna görə də toplama qaydasına əsasən, cavab bu hasillərin cədvəlin bütün xanaları üzrə cəminə bərabərdir.

Qalır ki, bu cəmi $9929$ moduluna görə hesablayaq:

i = 1 \sum n j = 1 \sum n a_{ij} \cdot b_{ij} mod 9929

\sum_{i=1}^{n} \sum_{j=1}^{n} a_{ij} \cdot b_{ij} \bmod 9929

Nümunə

$n = 3$ n = 3 üçün $a$ və $b$ massivlərini quraq. $a$ massivi yuxarıdan aşağıya və soldan sağa dolur. $b$ massivi isə əks qaydada, $b [3] [3] = 1$ b[3][3] = 1-dən başlayaraq dolur. Üçüncü cədvəldə $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j] hasilləri verilmişdir.

Məsələn, Xoca mərkəzi $(2, 2)$ xanasına iki üsulla çata bilər ( $a [2] [2] = 2$ a[2][2] = 2), eşşək də eyni qaydada ( $b [2] [2] = 2$ b[2][2] = 2). Buna görə də onlar bu xanada $2 \cdot 2 = 4$ 2 \cdot 2 = 4 üsulla görüşə bilərlər.

Xoca əvvəlcə yuxarı sol xanadadır ( $a [1] [1] = 1$ a[1][1] = 1), eşşək isə ora altı üsulla çata bilər ( $b [1] [1] = 6$ b[1][1] = 6), bu da $6$ üsul verir.

Hasilləri bütün xanalar üzrə cəmləyərək, cavabı alırıq:

i = 1 \sum 3 j = 1 \sum 3 a_{ij} \cdot b_{ij} = (6 + 3 + 1) + (3 + 4 + 3) + (1 + 3 + 6) = 30

\sum_{i=1}^{3} \sum_{j=1}^{3} a_{ij} \cdot b_{ij} = (6 + 3 + 1) + (3 + 4 + 3) + (1 + 3 + 6) = 30

Alqoritmin reallaşdırılması

İşçi massivləri elan edək:

$a [i] [j]$ — Xocanın $(1, 1)$ xanasından $(i, j)$ xanasına qədər olan yollarının sayı,
$b [i] [j]$ — eşşəyin $(n, n)$ xanasından $(i, j)$ xanasına qədər olan yollarının sayı.

Bütün qiymətlər $M O D = 9929$ MOD = 9929 moduluna görə saxlanılır. Massivlərin ölçüsü $M A X = 55$ MAX = 55-dir.

#define MAX 55
#define MOD 9929
int a[MAX][MAX], b[MAX][MAX];

Cədvəlin ölçüsü $n$ -i oxuyaq. $a$ və $b$ massivlərini sıfırlarla dolduraq.

scanf("%d", \&n);
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));

$a$ massivinin qiymətlərini hesablayaq.

a[1][1] = 1;
for (i = 1; i \u003c= n; i++)
for (j = 1; j \u003c= n; j++)
  a[i][j] = (a[i][j] + a[i - 1][j] + a[i][j - 1]) % MOD;

$b$ massivinin qiymətlərini hesablayaq.

b[n][n] = 1;
for (i = n; i \u003e= 1; i--)
for (j = n; j \u003e= 1; j--)
  b[i][j] = (b[i][j] + b[i + 1][j] + b[i][j + 1]) % MOD;

$r es$ dəyişənində $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j] hasillərinin cədvəlin bütün xanaları üzrə cəmini — Xoca ilə eşşəyin görüşə biləcəyi üsulların sayını hesablayaq.

res = 0;
for (i = 1; i \u003c= n; i++)
for (j = 1; j \u003c= n; j++)
  res = (res + a[i][j] * b[i][j]) % MOD;

Cavabı çap edək.

printf("%d\n", res);