Ходжа Насреддін#5101

Ходжа Насреддін (Розбір)

Ходжа й ослик зустрічаються в деякій клітинці $(i, j)$ таблиці. Спосіб зустрічі визначається трьома складовими: клітинкою зустрічі, маршрутом Ходжі з клітинки $(1, 1)$ до цієї клітинки та маршрутом ослика з клітинки $(n, n)$ до неї. Тому для кожної клітинки порахуємо кількість маршрутів Ходжі та ослика, що ведуть до неї.

Нехай $a [i] [j]$ — кількість шляхів, якими Ходжа може потрапити з клітинки $(1, 1)$ до клітинки $(i, j)$ . Ходжа рухається лише праворуч або вниз, тому до клітинки $(i, j)$ він потрапляє або з клітинки $(i - 1, j)$ (i - 1, j), що розташована над нею, або з клітинки $(i, j - 1)$ (i, j - 1), що розташована ліворуч від неї:

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

Клітинки поза межами таблиці недосяжні; кількість шляхів до них вважається рівною нулю.

Аналогічно, нехай $b [i] [j]$ — кількість шляхів, якими ослик може потрапити з клітинки $(n, n)$ до клітинки $(i, j)$ . Ослик рухається лише ліворуч або вгору, тому до клітинки $(i, j)$ він потрапляє або з клітинки $(i + 1, j)$ (i + 1, j), що розташована під нею, або з клітинки $(i, j + 1)$ (i, j + 1), що розташована праворуч від неї:

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

Маршрути Ходжі та ослика обираються незалежно один від одного. Тому за правилом добутку кількість способів зустрітися в клітинці $(i, j)$ дорівнює $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j]. Зустрічі в різних клітинках є різними способами, тому за правилом суми відповідь дорівнює сумі таких добутків за всіма клітинками таблиці.

Залишається обчислити цю суму за модулем $9929$ :

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 = 3$ n = 3 побудуємо масиви $a$ та $b$ . Масив $a$ заповнюється зверху вниз і зліва направо. Масив $b$ заповнюється у зворотному порядку, починаючи з $b [3] [3] = 1$ b[3][3] = 1. Третя таблиця містить добутки $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j].

Наприклад, Ходжа може дістатися центральної клітинки $(2, 2)$ двома способами ( $a [2] [2] = 2$ a[2][2] = 2), так само як і ослик ( $b [2] [2] = 2$ b[2][2] = 2). Отже, вони можуть зустрітися в цій клітинці $2 \cdot 2 = 4$ 2 \cdot 2 = 4 способами.

Ходжа спочатку знаходиться у верхній лівій клітинці ( $a [1] [1] = 1$ a[1][1] = 1), а ослик може дістатися до неї шістьма способами ( $b [1] [1] = 6$ b[1][1] = 6), що дає $6$ способів.

Підсумувавши добутки за всіма клітинками, отримуємо відповідь:

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

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

Оголосимо робочі масиви:

$a [i] [j]$ — кількість шляхів Ходжі з клітинки $(1, 1)$ до клітинки $(i, j)$ ,
$b [i] [j]$ — кількість шляхів ослика з клітинки $(n, n)$ до клітинки $(i, j)$ .

Усі значення зберігаються за модулем $M O D = 9929$ MOD = 9929. Розмір масивів — $M A X = 55$ MAX = 55.

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

Зчитаємо розмір таблиці $n$ . Заповнимо масиви $a$ та $b$ нулями.

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

Обчислимо значення масиву $a$ .

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

Обчислимо значення масиву $b$ .

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

У змінній $r es$ обчислимо суму добутків $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j] за всіма клітинками таблиці — кількість способів, якими Ходжа й ослик можуть зустрітися.

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

Виведемо відповідь.

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