Spion (ONI X)

Rezumatul enunțului:

Te afli în vârful unei piramide, ca cea din figură, de înălțime n (n $\leq$ 10^5). La fiecare pas, cobori cu un nivel mai jos (de la nivelul i la i+1), mergând spre vest (identificat cu litera V) sau est (identificat cu E). Poziția ta astfel poate fi identificată prin nivelul și coloana la care te afli la un moment dat.

Cerință:

Dându-se un traseu de tipul celui din enunț, determină coloana la care te vei afla la sfârșitul traseului, precum și în cate moduri poți ajunge în acea poziție, modulo 100003.

De exemplu, pentru VEEVE, coloana finală este 4, iar numărul de moduri prin care poți ajunge acolo este 10.

Soluție:

Să studiem ce înseamnă mai exact mișcările spre vest și spre est în piramidă. Observăm că, atunci când facem un pas în jos, spre vest, numărul coloanei la care ne aflăm nu se schimbă, în timp ce, atunci când ne deplasăm pe est, acesta crește cu unu. Astfel, indicele coloanei la care ne vom afla la final este egal cu numărul de litere E din traseul dat plus unu (căci pornim de la coloana 1).

Fie k numărul de litere E din traseu. Remarcăm că poziția finală depinde doar de numărul de pași spre est și nu de momentele sau ordinea în care sunt făcuți. Așadar, vom avea $C_\text{ lungimea traseului} ^ \text{ numarul de litere E}$ moduri în care putem ajunge la poziția finală, adică $C_{n}^{k}$ , reprezentând combinările de $n$ elemente luate câte $k$ , fiind egale cu $\frac{n!}{k!(n-k)!}$ .

Problema însă nu este gata. Cum calculăm aceste combinări? Acest număr crește foarte repede (pentru n = 100 și k = 50, de exemplu, până și tipul de date unsigned long long face overflow), așa că varianta de a îl calcula într-o manieră ,,clasică”, la sfârșit afișându-l modulo 100003 este exclusă. O primă idee ar fi să folosim triunghiul lui Pascal, folosindu-ne de recurența $C_{n}^{k} = C_{n-1}^{k} + C_{n-1}^{k-1}$ . Astfel, putem utiliza o matrice c, cu semnificația c[i][j] = $C_{i}^{j} \text { mod } 100003$ și recurența devine c[i][j] = (c[i-1][j] + c[i-1][j-1]) mod 100003. Problema este că rezolvarea acestei recurențe se face în $O(n^2)$ , ceea ce este mult prea lent pentru n > 2000, deci e nevoie de o altă strategie.

Să ne întoarcem la formula $C_{n}^{k} = \frac{n!}{k!(n-k)!}$ . Având în vedere că n $\leq$ 100000, putem calcula cu o simplă buclă for produsele din numitorul și numărătorul acestei fracții, totul modulo 100003. Deci $C_{n}^{k} = \frac {A}{B}$ , unde A și B resturi cunoscute la împărțirea la 100003. Poate părea intuitiv să împărțim pur și simplu A la B și să considerăm câtul obținut răspunsul final, însă nu este corect. De exemplu, dacă am vrea să aflăm câtul împărțirii lui 100004 (al cărui rest la 100003 este 1) la 50002, folosind acest raționament am obține răspunsul 0, deși cel corect este 2. Vom apela la un concept numit invers modular, care face această împărțire în mod corect, totul modulo 100003.

Pornim de la teorema lui Euler, conform căreia $a^{\varphi(r)} \equiv 1 \text { (mod } r \text{)}$ (unde $\varphi(r)$ este indicatorul lui Euler, adică numărul de numere mai mici ca $r$ și prime față de $r$ ). Să aranjăm un pic termenii:

$a^{\varphi(r)} \equiv 1 \text { (mod } r \text{)} \Leftrightarrow a^{\varphi(r)-1} \cdot a \equiv 1 \text { (mod } r \text{)} \Leftrightarrow a^{\varphi(r)-1} \equiv \frac {1}{a} \text { (mod } r \text{)}$

Fracția $\frac{1}{a}$ se numește inversul modular al lui $a$ , modulo $r$ . Pentru $r = 100003$ , trebuie să ridicăm numărul B la puterea $\varphi(100003)-1$ , pentru a afla inversul modular. Fiindcă 100003 este prim, $\varphi(100003) = 100002$ , iar ridicarea la putere se poate face iterativ (folosind simplul for) sau logaritmic.