Hodja Nasreddin#5101

Hodja Nasreddin (Editoriale)

Hodja e l'asino si incontrano in una qualche cella $(i, j)$ della tabella. Un modo di incontro è determinato da tre componenti: la cella d'incontro, il percorso di Hodja dalla cella $(1, 1)$ fino a questa cella, e il percorso dell'asino dalla cella $(n, n)$ fino ad essa. Pertanto, per ogni cella contiamo il numero di percorsi di Hodja e dell'asino che vi conducono.

Sia $a [i] [j]$ il numero di percorsi con cui Hodja può arrivare dalla cella $(1, 1)$ alla cella $(i, j)$ . Hodja si muove solo verso destra o verso il basso, quindi entra nella cella $(i, j)$ o dalla cella $(i - 1, j)$ (i - 1, j) situata sopra di essa, oppure dalla cella $(i, j - 1)$ (i, j - 1) situata alla sua sinistra:

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

Le celle al di fuori della tabella sono irraggiungibili; il numero di percorsi verso di esse è considerato pari a zero.

Analogamente, sia $b [i] [j]$ il numero di percorsi con cui l'asino può arrivare dalla cella $(n, n)$ alla cella $(i, j)$ . L'asino si muove solo verso sinistra o verso l'alto, quindi entra nella cella $(i, j)$ o dalla cella $(i + 1, j)$ (i + 1, j) situata sotto di essa, oppure dalla cella $(i, j + 1)$ (i, j + 1) situata alla sua destra:

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 percorsi di Hodja e dell'asino vengono scelti in modo indipendente l'uno dall'altro. Pertanto, per la regola del prodotto, il numero di modi per incontrarsi nella cella $(i, j)$ è uguale a $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j]. Gli incontri in celle diverse sono modi diversi, quindi per la regola della somma, la risposta è uguale alla somma di tali prodotti su tutte le celle della tabella.

Non resta che calcolare questa somma 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

Esempio

Per $n = 3$ n = 3, costruiamo gli array $a$ e $b$ . L'array $a$ viene riempito dall'alto verso il basso e da sinistra verso destra. L'array $b$ viene riempito nell'ordine inverso, a partire da $b [3] [3] = 1$ b[3][3] = 1. La terza tabella contiene i prodotti $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j].

Ad esempio, Hodja può raggiungere la cella centrale $(2, 2)$ in due modi ( $a [2] [2] = 2$ a[2][2] = 2), e lo stesso vale per l'asino ( $b [2] [2] = 2$ b[2][2] = 2). Pertanto, possono incontrarsi in questa cella in $2 \cdot 2 = 4$ 2 \cdot 2 = 4 modi.

Hodja si trova inizialmente nella cella in alto a sinistra ( $a [1] [1] = 1$ a[1][1] = 1), e l'asino può raggiungerla in sei modi ( $b [1] [1] = 6$ b[1][1] = 6), il che dà $6$ modi.

Sommando i prodotti su tutte le celle, otteniamo la risposta:

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

Implementazione dell'algoritmo

Dichiariamo gli array di lavoro:

$a [i] [j]$ — il numero di percorsi di Hodja dalla cella $(1, 1)$ alla cella $(i, j)$ ,
$b [i] [j]$ — il numero di percorsi dell'asino dalla cella $(n, n)$ alla cella $(i, j)$ .

Tutti i valori sono memorizzati modulo $M O D = 9929$ MOD = 9929. La dimensione degli array è $M A X = 55$ MAX = 55.

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

Leggiamo la dimensione della tabella $n$ . Riempiamo gli array $a$ e $b$ con zeri.

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

Calcoliamo i valori dell'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;

Calcoliamo i valori dell'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;

Nella variabile $r es$ , calcoliamo la somma dei prodotti $a [i] [j] \cdot b [i] [j]$ a[i][j] \cdot b[i][j] su tutte le celle della tabella — il numero di modi in cui Hodja e l'asino possono incontrarsi.

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

Stampiamo la risposta.

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