Hodja Nasreddin#5101

Hodja Nasreddin (Editorial)

Hodja and the donkey meet in some cell $(i, j)$ of the table. A way of meeting is determined by three components: the meeting cell, Hodja's route from cell $(1, 1)$ to this cell, and the donkey's route from cell $(n, n)$ to it. Therefore, for each cell we count the number of Hodja's and the donkey's routes leading to it.

Let $a [i] [j]$ be the number of paths by which Hodja can get from cell $(1, 1)$ to cell $(i, j)$ . Hodja moves only right or down, so he enters cell $(i, j)$ either from cell $(i - 1, j)$ (i - 1, j) located above it, or from cell $(i, j - 1)$ (i, j - 1) located to the left of it:

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

Cells outside the table are unreachable; the number of paths to them is considered to be zero.

Similarly, let $b [i] [j]$ be the number of paths by which the donkey can get from cell $(n, n)$ to cell $(i, j)$ . The donkey moves only left or up, so it enters cell $(i, j)$ either from cell $(i + 1, j)$ (i + 1, j) located below it, or from cell $(i, j + 1)$ (i, j + 1) located to the right of it:

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

Hodja's and the donkey's routes are chosen independently of each other. Therefore, by the rule of product, the number of ways to meet in cell $(i, j)$ equals $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j]. Meetings in different cells are different ways, so by the rule of sum, the answer equals the sum of such products over all cells of the table.

It remains to compute this sum modulo $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

Example

For $n = 3$ n = 3, let us build the arrays $a$ and $b$ . The array $a$ is filled from top to bottom and from left to right. The array $b$ is filled in reverse order, starting from $b [3] [3] = 1$ b[3][3] = 1. The third table contains the products $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j].

For example, Hodja can reach the central cell $(2, 2)$ in two ways ( $a [2] [2] = 2$ a[2][2] = 2), and so can the donkey ( $b [2] [2] = 2$ b[2][2] = 2). Therefore, they can meet in this cell in $2 \cdot 2 = 4$ 2 \cdot 2 = 4 ways.

Hodja is initially in the upper left cell ( $a [1] [1] = 1$ a[1][1] = 1), and the donkey can reach it in six ways ( $b [1] [1] = 6$ b[1][1] = 6), which gives $6$ ways.

Summing the products over all cells, we get the answer:

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

Algorithm implementation

Declare the working arrays:

$a [i] [j]$ — the number of Hodja's paths from cell $(1, 1)$ to cell $(i, j)$ ,
$b [i] [j]$ — the number of the donkey's paths from cell $(n, n)$ to cell $(i, j)$ .

All values are stored modulo $M O D = 9929$ MOD = 9929. The size of the arrays is $M A X = 55$ MAX = 55.

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

Read the size of the table $n$ . Fill the arrays $a$ and $b$ with zeros.

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

Compute the values of the array $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;

Compute the values of the array $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;

In the variable $r es$ , compute the sum of the products $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j] over all cells of the table — the number of ways in which Hodja and the donkey can meet.

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

Print the answer.

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