Elemente de Combinatorica

autor: Bogdan Iordache

Combinatorica este o ramura a matematicii care se ocupa cu studiul structurilor finite si al proprietatilor acestora. Este “unealta” care sta la baza rezolvarii problemelor de numarare.

Produs cartezian si numarare de functii

Fie $A$ si $B$ doua multimi finite. Definim produsul cartezian al acestor multimi astfel:
$A \times B = \{(a, b) | a \in A, b \in B\}$
De exemplu:
$\{a_1, a_2, a_3\} \times \{b_1, b_2\} = \{(a1, b1), (a1, b2), (a2, b1), (a2, b2), \\(a3, b1), (a3, b2)\}$

Cu alte cuvinte, produsul cartezian al doua multimi ( $A$ si $B$ ) este multimea de perechi construite punand elemente din $A$ pe prima pozitie si elemente din $B$ pe a doua pozitie. Astfel imperechem fiecare element din $A$ cu fiecare element din $B$ .

Consideram acum $n$ multimi: $A_1, A_2, \ldots, A_n$ . Produsul cartezian al $n$ multimi este multimea de $n$ -tupluri in care pe prima pozitie avem element din $A_1$ , pe a doua pozitie avem element din $A_2$ s.a.m.d.

$A_1 \times A_2 \times \ldots \times A_n = \{(a_1, a_2, \ldots, a_n) | a_1 \in A_1, a_2 \in A_2, \ldots, a_n \in A_n\}$

Intrebare: Cate elemente are multimea $A \times B$ ? Dar $A_1 \times A_2 \times \ldots \times A_n$ ?
$|A \times B| = |A| \cdot |B|$
$|A_1 \times A_2 \times \ldots \times A_n| = |A_1| \cdot |A_2| \cdot \ldots \cdot |A_n|$

O functie $f: A \rightarrow B$ atribuie fiecarui element din $A$ un element din $B$ (nu neaparat in mod unic).
Exemplu
Intrebare: Cunoscand multimile $A$ si $B$ , cate astfel de functii exista?
Notam $n = |A|$ si $m = |B|$ . O functie de la $A$ la $B$ este echivalenta cu un $n$ -tuplu de elemente din multimea $B$ . De ce?

Daca consideram $A = \{a_1, a_2, \ldots, a_n\}$ si $B = \{b_1, b_2, \ldots, b_m\}$ si un $n$ -tuplu ( $b_{i_1}, b_{i_2}, \ldots, b_{i_n})$ , format din elemente din $B$ ( $i_1, i_2, \ldots, i_n$ sunt indici de la $1$ la $m$ , nu neaparat distincti), putem vedea imediat ca acestui tuplu ii putem asocia in mod unic o functie $f: A \rightarrow B$ , cu $f(a_k) = b_{i_k}, k=\overline{1, n}$ .

Deci pentru a numara functiile, putem numara tuplurile. Insa aceste tupluri nu sunt altceva decat elementele produsului cartezian cu $n$ termeni $B \times B \times \ldots \times B$ , al carui cardinal este $m^n = |B|^{|A|}$ .

In concluzie avem un total de $|B|^{|A|}$ functii de la $A$ la $B$ .

Aplicatie Fie o multime cu $n$ elemente $A = \{a_1, a_2, \ldots, a_n\}$ . Cate submultimi are aceasta multime?

Putem interpreta constructia unei submultimi astfel: pentru fiecare element din $A$ am doua optiuni, fie aleg sa nu adaug acel element la submultimea mea ( $0$ ), fie il adaug ( $1$ ).

Observam astfel ca o submultime nu este altceva decat o functie care atribuie fiecarui element din $A$ o valoare din multime $\{0, 1\}$ . Cum numarul acestor functii este $2^n$ , acesta este si numarul de submultimi.

Permutari

Permutarile unei multimi se definesc ca toate posibilitatile de a aranja toate elementele multimii intr-un sir.

De exemplu, permutarile multimii $\{1, 2, 3\}$ sunt:

$1,2,3$
$1,3,2$
$2,1,3$
$2,3,1$
$3,1,2$
$3,2,1$

Intrebare: Cate permutari are o multime cu $n$ elemente?
Vom raspunde la aceasta intrebare printr-o serie de mai multe intrebari si raspunsuri :)

in cate moduri pot alege primul element din permutare? R: in $n$ moduri, pot incepe permutarea cu orice element din $A$
avand fixat primul element, in cate moduri pot alege cel de-al doilea element? R: in $n-1$ moduri, intrucat nu mai am voie sa il folosesc pe primul
$\ldots$
avand fixate primele $n-1$ elemente, in cate moduri pot alege cel de-al $n$ -lea element? R: intr-un singur mod, intrucat nu mai am voie sa folosesc niciunul din cele $n-1$ elemente deja fixate.

Avem deci numarul total de permutari egal cu $n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 = n!$ . Acest numar se mai noteaza cu $P_n$ .

Aranjamente

Fie o multime cu $n$ elemente si un numar natural $m \leq n$ . Un aranjament de dimensiune $m$ al multimii este orice sir de $m$ elemente distincte din aceasta multimie.

De exemplu, aranjamentele de dimensiune $2$ ale multimii $\{1,2,3,4\}$ sunt:

$1, 2$
$1, 3$
$1, 4$
$2, 1$
$2, 3$
$2, 4$
$3, 1$
$3, 2$
$3, 4$
$4, 1$
$4, 2$
$4, 3$

Numarul aranjamentelor de dimensiune $m$ ale unei multimi cu $n$ elemente se mai noteaza $A_n^m$ (se citeste "aranjamente de $n$ , luate cate $m$ ").

Intrebare: Pentru $n$ si $m$ date, cate astfel de aranjamente exista?
Pentru a gasi numarul de aranjamente vom parcurge aceeasi pasi ca la numarul de permutari, oprindu-ne insa la cea de $m$ -a intrebare:

in cate moduri pot alege primul element din aranjament? R: in $n$ moduri, pot incepe aranjamentul cu orice element din $A$
avand fixat primul element, in cate moduri pot alege cel de-al doilea element? R: in $n-1$ moduri, intrucat nu mai am voie sa il folosesc pe primul
$\ldots$
avand fixate primele $m-1$ elemente, in cate moduri pot alege cel de-al $m$ -lea element? R: in $n-m+1$ moduri, intrucat nu mai am voie sa folosesc niciunul din cele $m-1$ elemente deja fixate.

Avem astfel: $A_n^m = n \cdot (n-1) \cdot \ldots \cdot (n-m+1) = \frac{n!}{(n-m)!}$ .

Combinari

O combinare de dimensiune $m$ a unei multimi cu $n$ elemente este o submultime de cardinal $m$ a acesteia.

De exemplu, combinarile de dimensiune $3$ ale multimii $\{1,2,3,4\}$ sunt:

$1,2,3$
$1,2,4$
$1,3,4$
$2,3,4$

Numarul acestor combinari se noteaza $C_n^m$ si se citeste "combinari de $n$ luate cate $m$ ".

Intrebare: Pentru $n$ si $m$ date, cate astfel de combinari exista?
Pentru a rezolva aceasta problema, trebuie sa vedem care este legatura dintre combinari si aranjamente. La aranjamente ordinea elementelor alese conteaza, pe cand la combinari, nu.

$1,2,3$ si $3,1,2$ sunt aranjamete diferite, dar sunt aceeasi combinare.

Fiecarei combinari ii putem asocia in mod unic un numar fix de aranjamente, pe care le putem genera permutand in toate modurile posibile elementele combinarii. Avem astfel ca pentru o combinare putem genera $m!$ aranjamente. Cum un aranjament poate fi generat de o singura combinare, avem ca numarul de aranjamente este de $m!$ de ori mai mare decat numarul de combinari.

Asadar, $C_n^m = \frac{A_n^m}{m!} = \frac{n!}{m!(n-m)!}$

Aplicatie La un turneu individual de tenis participa N concurenti. Stim ca fiecare jucator va desfasura cate un meci cu fiecare alt jucator. Cate meciuri vor avea loc?
R: $C_N^2$ (de ce?)

Aplicatie Cate siruri binare de $n$ biti au exact $m$ biti de $1$ ?
R: $C_n^m$ (de ce?)

Cum implementam calculul acestor valori?

Toate formulele discutate duc deobicei la numere foarte mari (de exemplu, $14! = 87,178,291,200$ ). In probleme veti intalni de cele mai multe ori o exprimare asemanatoare cu: “intrucat raspunsul poate deveni foarte mare, returnati restul impartirii acestuia la un numar MOD”.

Numarare de functii / produs cartezian

In acest caz, vrem sa calculam formula $(m^n)\ \%\ MOD$ .

Varianta $O(n)$ :

int res = 1;
for (int i = 1; i <= n; i++)
	res = (res * m) % MOD;

Acest calcul se poate face mai rapid in complexitate $O(log\ n)$ , insa pentru aceasta tehnica trebuie sa revizuiti materialul de la capitolul “Divide et Impera” :) .

Numarul de permutari

Vrem sa calculcam $n!\ \%\ MOD$ . Nimic mai simplu decat o implementare in $O(n)$ :

int res = 1;
for (int i = 1; i <= n; i++)
	res = (res * i) % MOD;

Numarul de aranjamente

Vrem sa calculcam $\frac{n!}{(n-m)!}\ \%\ MOD$ .
Problema la acest calcul este operatia de impartire. Reamintim urmatoarele identitati pentru calculul cu resturi:

$(A + B)\ \%\ MOD = ((A\ \%\ MOD) + (B\ \%\ MOD))\ \%\ MOD$
$(A \cdot B)\ \%\ MOD = ((A\ \%\ MOD) \cdot (B\ \%\ MOD))\ \%\ MOD$
pentru operatia de scadere, putem mereu sa ne folosim de faptul ca $(-A)\ \%\ MOD = MOD - A\ \%\ MOD$ , pentru $A$ intreg pozitiv

Insa la impartire nu putem spune ca $\frac{A}{B}\ \%\ MOD$ si $\frac{A\ \%\ MOD}{B\ \%\ MOD}\ \%\ MOD$ dau acelasi rezultat (incercati de exemplu $A=21, B=7, MOD=5$ ).

Exista tehnici pentru a calcula restul impartirii pentru fractii unde cunoastem doar resturile numaratorului si numitorului. Acestea insa depasesc pentru moment scopul acestei prezentari, dar daca doriti sa investigati mai departe, un punct bun de plecare este problema Invers modular de pe infoarena si indicatiile de rezolvare de aici.

Revenind la aranjamente, formula ne permite totusi sa o calculam usor in $O(n)$ :

int res = 1;
for (int i = n - m + 1; i <= n; i++)
	res = (res * i) % MOD;

Numarul de combinari

Vrem sa calculcam $\frac{n!}{m!(n-m)!}\ \%\ MOD$ .

Aici din pacate nu mai avem o metoda simpla de a scapa de impartire, insa ne vom folosi de urmatoarea identitate:
$C_n^m = C_{n-1}^m + C_{n-1}^{m-1}$
Demonstratie identitatii este imediata (se inlocuiesc formulele si se aduce la acelasi numitor in membrul drept).

Aceasta formula ne permite sa calculam matricea $C[i][j]$ cu semnificatia $C[i][j] = C_i^j$ . Putem astfel calcula toate combinarile cu $0 \leq j \leq i \leq n$ .

C[0][0] = 1 //combinari de 0 luate cate 0 = 1 (prin conventie)
for (int i = 1; i <= n; i++)
	for (int j = 0; j<= i; j++)
		C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
cout << C[n][m];

Aceasta tehnica mai poarta numele de Triunghiul lui Pascal. Un exemplu de calcul gasiti mai jos:
enter image description here

ATENTIE!! Aveti girja la calculele care pot duce la overflow. Atunci cand calculati (a*b)%MOD, chiar daca a, b si MOD sunt de tip int, inmultirea din paranteza poate depasi limita de $2^{31}$ . Un truc comun este de a forta calculul din paranteza sa fie facut pe tipul de date long long inmultind la inceput cu literalul 1LL (numarul $1$ dar pe tipul long long): (1LL * a * b) % MOD.

Probleme propuse

1. Munte5 (infoarena)

Vom incepe cu cateva observatii care garanteaza existenta a macar unei structuri de munte care se poate forma:

valoarea maxima trebuie sa fie unica, altfel daca am avea de exemplu doua valori maxime, una nu ar fi vizibila din stanga, in timp ce cealalta nu ar fi vizibila din dreapta, fiind obturata de perechea ei.
valoarea maxima ne separa sirul astfel incat la stanga ei trebuie sa avem un sir strict crescator, iar la dreapta unul strict descrescator; de aici observam ca daca o valoare apare de doua ori suntem obligati sa ii punem o aparitie in partea stanga, iar cealalalta aparitie in partea dreapta; daca o valoare apare de cel putin $3$ ori atunci nu avem solutie (suntem obligati sa avem macar doua aparitii ale ei fie in stanga, fie in dreapta, astfel nu mai putem obtine un sir strict monoton in acea parte).

Odata ce stabilim ce valori punem in stanga maximului si ce valori punem in dreapta maximului structura de munte este unic determinata.

Pentru valorile care apar de doua ori nu avem ce decizie sa luam, am vazut mai devreme ca una dintre ele ajunge in partea stanga, iar cealalta in partea dreapta. Notam cu unic numarul de valori care apar o singura data in sirul dat la input (cu exceptia valorii maxime!). Putem alege acum orice submultime a acestora sa fie pusa in stanga maximului, iar complementara ei sa fie pusa in dreapta. Numarul de moduri de a face acest lucru este chiar numarul de submultimi ( $2^{unic}$ ).

Atentie la cazul in care toate valorile din sirul de la input apar o singura data. Formula de mai sus va numara si cazul in care maximul este primul element al muntelui (submultimea aleasa pentru partea stanga este submultimea vida), sau ultimul (submultimea aleasa pentru partea stanga este multimea tuturor valorilor), aceste doua cazuri trebuie scazute de la rezultat. Daca avem cel putin o valoare cu doua aparitii, acest caz particular nu mai apare, deoarece avem garantat ca de-a stanga si de-a dreapta maximului avem cel putin o valoare.

2. Cod2 (infoarena)

Folosim urmatoarele notatii:
$nrlit$ : numarul de litere distincte din sirul de la intrare
$unic$ : numarul de litere distincte care apar o singura data in sirul de intrare
$poli$ : numarul de litere distincte care apar de cel putin doua ori in sirul de intrare
Evident $nrlit = unic + poli$

Vom imparti numararea codurilor in cele doua cazuri descrise in problema.

a. pentru a numara cate coduri de lungime $n$ cu toate literele distincte putem forma, este echivalent cu a numara aranjamentele de lungime $n$ ale multimii de litere. Astfel avem $A_{nrlit}^n$ astfel de coduri.

b. pentru cazul in care in cod avem exact o litera care apare pe doua pozitii, numararea o putem face impartind pasii independenti care duc la constructia unui astfel de cod:

fixam litera care apare de doua ori in cod (in cate moduri putem face acest lucru?.. in $poli$ moduri, oricare din aceste litere poate fi aleasa sa apara de doua ori)
avand aceasta litera fixata, alegem cele doua pozitii din totalul de $n$ pe care o vom plasa, acest lucru poate fi facut in $C_n^2$ moduri (ordinea pozitiilor alese nu conteaza, daca alegem pozitiile “3 si 5” sau “5 si 3” am facut de fapt aceeasi alegere)
mai avem acum de completat restul de $n-2$ pozitii cu litere distincte; mai avem la dispozitie $nrlit-1$ litere inca nefolosite, asadar putem completa restul pozitiilor in $A_{nrlit-1}^{n-2}$ moduri.

Din a. si b. obtinem ca numarul total de coduri posibile este:
$ $A_{nrlit}^n + poli \cdot C_n^2 \cdot A_{nrlit-1}^{n-2}$

3. Stars and Bars (pbinfo)

Problema este echivalenta cu a numara in cate moduri putem scrie numarul $n$ ca suma de $k$ valori naturale ( $\geq 0$ ). De exemplu, pentru numarul $n=5$ si $k=3$ urmatoarele sunt cateva exemple de astfel de scrieri:

$5 = 2 + 2 + 1$
$5 = 1 + 2 + 2$
$5 = 2 + 0 + 3$
$5 = 0 + 0 + 5$

Cum putem numara aceste scrieri. Va vine sa credeti sau nu, aceasta problema se rezolva cu ajutorul combinarilor. Pentru a face explicatia mai usoara si pentru ca “o poza face cat o mie de cuvinte”, mai jos puteti vedea cum interpretam o astfel de scriere ca un numar in baza 2:

stars and bars
Vedem cum scrierea lui $n$ ca suma de $k$ numere poate fi vizualizata ca un sir de $n$ obiecte separate de $k-1$ bare verticale. Daca notam obiectele cu $0$ si barele cu $1$ obtinem o corespondenta de unu-la-unu intre aceste scrieri si sirurile de $n + k - 1$ biti cu exact $k-1$ biti de $1$ .

Dar cate astfel de siruri exista? $C_{n+k-1}^{k-1}$

4. Suma si numarul divizorilor (infoarena)

a. Numarul de divizori Consideram descompunerea lui $n$ in factori primi:
$n = p_1^{s_1} \cdot p_2^{s_2} \cdot \ldots \cdot p_k^{s_k}$

Un divizor al lui $n$ va arata astfel:
$d = p_1^{t_1} \cdot p_2^{t_2} \cdot \ldots \cdot p_k^{t_k} \\ t_1 \leq s_1, t_2 \leq s_2, \ldots ,t_k \leq s_k$

Cu alte cuvinte, divizorul nu are voie sa contina in descompunerea sa alti factori primi decat $n$ , iar exponentul acestora trebuie sa fie mai mic sau egal cu cel din decompunerea lui $n$ (posibil si $0$ , intrucat divizorul poate sa nu contina anumiti factori primi din descompunerea lui $n$ ).

Ramane acum sa numaram in cate moduri putem fixa sirul $(t_1, t_2, \ldots , t_k)$ . Intrucat pentru $t1$ avem $s_1 + 1$ posibilitati (numerele de la $0$ la $s_1$ ), pentru $t_2$ avem $s_2 + 1$ posibilitati s.a.m.d, obtinem formula pentru numarul de divizori:
$(s_1 + 1)(s_2 + 1)\ldots(s_k+1) = \prod_{i=1}^{k}(s_i+1)$

b. Suma divizorilor Consideram aceeasi descompunere pentru $n$ . Formula de mai jos ne da suma divizorilor:

$(p_1^0 + p_1^1 + \ldots + p_1^{s_1})(p_2^0 + p_2^1 + \ldots + p_2^{s_2})\ldots(p_k^0 + p_k^k + \ldots + p_k^{s_k})$

Demonstratia este faptul ca daca am desface parantezele fiecare termen al sumei finale ar fi un produs intre cate un element din fiecare paranteza. Cum in fiecare paranteza avem factori primi la puteri mai mici sau egale decat cea cu care apar in descompunerea lui $n$ , toti termenii pe care ii obtinem reprezinta divizorii lui $n$ .

Ca implementare, dupa ce determinam descompunerea lui $n$ putem calcula fiecare paranteza separat, apoi inmultim rezultatele.

Se poate folosi si faptul ca in paranteze avem sume de progresii geometrice, folosind acest fapt putem reduce formula la:
$\prod_{i=1}^k \frac{p_i^{s_i + 1} - 1}{p_i - 1}$
Insa rezultatul cerut de problema este restul impartirii acestei formule la $9973$ iar, asa cum am vazut mai devreme, faptul ca termenii produsului sunt fractii nu ne ajuta sa le calculam restul impartirii fara a folosi tehnici legate de inversul modular.

Cu toate acestea, intrucat trebuie sa determinam oricum descompunerea lui $n$ , calculul primei forme nu ne afecteaza complexitatea finala.

5. Sandokan (infoarena)

Observam ca elementul maxim din sir va ramane tot timpul in configuratia finala. Datorita acestul fapt, la fiecare pas putem alege elementul maxim impreuna cu oricare alte $K-1$ elemente pe care le vom elimina. Deci daca configuratia finala contine $P$ elemente, unul din cele P elemente este elementul maxim, iar restul de $P-1$ le putem alege in toate modurile posibile.

Stiind ca la fiecare pas, se elimina $K-1$ elemente si ne oprim atunci cand numarul de elemente devine mai mic decat $K$ , putem gasi usor formula pentru $P = (N-1)\ \%\ (K - 1) + 1$ .

Cu observatiile de mai sus, aflam ca raspunsul la problema noastra este $C_{N-1}^{P-1}$ .

6. Multiplu2 (infoarena)

Observam usor ca un $K$ -sir trebuie sa contina doar divizori ai lui $N$ , altfel cmmmc-ul acestora nu va fi $N$ . Insa aceasta conditie nu este si suficienta, ci ne garanteaza doar ca cmmmc-ul $K$ -sirului il divide pe $N$ .

Fir $p$ un divizor prim al lui $N$ care apare la puterea $t$ in descompunerea lui $N$ in factori primi.

In cate moduri putem fixa exponentul lui $p$ in descompunerea celor $K$ numere din sir? Intrucat fiecare numar din sir il divide pe $N$ , putem sa ii fixam exponentul lui $p$ orice valoare intreaga din intervalul $[0,t]$ (in total $t+1$ variante). Avem $t+1$ variante pentru primul numar, $t+1$ variante pentru cel de-al doilea s.a.m.d., deci in total avem $(t+1)^K$ variante de a distribui exponentii lui $p$ printre numerele din $K$ -sir.

Problema este ca in aceasta formula numaram si cazurile in care toate cele $K$ numere primesc exponenti strict mai mici decat $t$ , iar daca pentru un astfel de $K$ -sir calculam cmmmc-ul, acesta va avea in descompunere $p$ la o putere mai mica decat $t$ , deci nu poate fi egal cu $N$ .

Numarul acestor cazuri gresite il putem afla similar, limitand acum exponentii doar la intervalul $[0,t-1]$ , deci in total am avea $t^K$ astfel de cazuri.

Am obtinut ca pentru un factor prim al lui $N$ ( $p$ ) care apare la puterea $t$ in descompunerea lui $N$ in factori primi avem $(t+1)^K - t^K$ variante de a seta exponentul lui $p$ in numerele din $K$ -sir, astfel incat garantam ca in descompunerea cmmmc-ului sirului, $p$ apare tot la puterea $t$ .

Numararile pe care le facem pentru un factor prim $p$ si pentru un factor prim $q$ sunt independente (ce exponenti setam pentru $p$ numerelor din $K$ -sir nu influenteaza ce exponenti setam pentru $q$ ). Astfel la numarul total de posibilitati aceste cazuri se vor inmulti.

Obtinem acum formula finala pentru numarul de $K$ -siruri corecte: $\prod_{i=1}^{m} [(t_i + 1)^K - t_i^K]$ , unde $N$ are descompunerea in factori primi $N = p_1^{t_1} \cdot p_2^{t_2} \cdot \ldots \cdot p_m^{t_m}$ .

Pentru a obtine $100$ de puncte, ridicarile la putere din formula trebuie facute in complexitate $O(log\ N)$ folosind divide et impera.

7. Tamplar (infoarena)

Problema ne cere de fapt cate ordonari putem realiza pentru cele $L-1$ taieturi. Ni se cere deci numarul de permutari de dimensiune $L-1$ , adica $(L-1)!$ .

Dificultatea problemei sta in faptul ca nu se mai cere rezultatul ca rest la impartirea cu un numar, ci se doreste valoarea exacta. Pentru aceasta, factorialul trebuie calculat folosind o reprezentare a numerelor cu oricat de multe cifre.

Un astfel de numar, pe care il numim deobicei numar “mare”, poate fi reprezentat usor folosind un vector de cifre. Fie $H$ acest vector, prin conventie putem considera ca $H[0]$ contine numarul de cifre al numarului “mare”, $H[1]$ contine cea mai nesemnificativa cifra (cea mai din dreapta), $H[2]$ a doua cea mai nesemnificativa, s.a.m.d. pana la $H[H[0]]$ care este cea mai semnificativa (prima) cifra a numarului.

Avand aceasta reprezentare, ne este usor acum sa implementam inmultirea dintre un numar “mare” si un numar “mic” (prin mic se intelege orice numar pe care il salvati intr-o variabila simpla). In tabelul de mai jos aveti un exemplu in care inmultim numarul “mare” $13572$ cu numarul “mic” $12$ .

	H[0]	H[1]	H[2]	H[3]	H[4]	H[5]	H[6]
initial	5	2	7	5	3	1
pas 1	5	*2 12 = 4 + 2 * 10**	7	5	3	1
pas 2	5	4	*7 12 + 2 = 6 + 8 * 10**	5	3	1
pas 3	5	4	6	*5 12 + 8 = 8 + 6 * 10**	3	1
pas 4	5	4	6	8	*3 12 + 6 = 2 + 4 * 10**	1
pas 5	5	4	6	8	2	*1 12 + 4 = 6 + 1 * 10**
pas 6	6	4	6	8	2	6	1

Obtinem ca rezultatul inmultirii este numarul $162864$ . Nu am facut altceva decat sa simulam pe acest vector inmultirea de mana. Aceasta ar fi o sugestie de implementare a unei functii care inmulteste un numar mare cu un numar mic:

void Mult(int H[], int X) {  // H <- H * X
	int T = 0;  // transportul (ce "tinem in minte")
	for (int i = 1; i <= H[0]; i++) {
		H[i] = H[i] * X + T;
		T = H[i] / 10;
		H[i] = H[i] % 10;
	}
	while (T) {  // cat timp mai exista transport
		H[0]++;
		H[H[0]] = T % 10;
		T = T / 10;
	}
}

Mai multe detalii despre lucrul cu numere “mari” puteti gasi in acest articol de pe infoarena, unde sunt detaliate toate operatiile de care ati avea nevoie sa le implementati vreodata.

8. Sistem (infoarena)

Problema ne cere sa numaram in cate moduri putem sa organizam orasele ca o multime de cicluri. Prin ciclu intelgem un mod de a uni o submultime de orase, astfel incat fiecare oras este unit cu alte doua si putem ajunge de la orice oras la orice alt oras din ciclu (imaginati-va ca orasele dintr-un ciclu sunt puse intr-un cerc, iar fiecare oras este unit cu vecinul din stanga si cu vecinul din dreapta sa).

O astfel de organizare pentru $10$ orase arata astfel:
enter image description here
Putem obtine o multime de alte configuratii, de exemplu toate orasele de la $1$ la $10$ puse intr-un singur ciclu: $1-2-3-\ldots-9-10-1$ .

Pentru a numara aceste configuratii vom defini urmatorul vector: $D[i]$ cu semnificatia in cate moduri putem organiza $i$ orase ca cicluri.

Raspunsul la problema noastra se va gasi in $D[N]$ .

Sa vedem acum cum arata $D[i]$ pentru valori mici ale lui $i$ :

$D[0] = 1$ , cu $0$ noduri avem o posibilitate de a le organiza ca cicluri (numaram acest caz prin conventie, reprezentand organizarea vida)
$D[1] = D[2] = 0$ , cu $1$ sau $2$ noduri nu putem forma niciun ciclu, deci nu avem nicio organizare corecta
$D[3] = 1$ , cu 3 noduri putem forma un singur ciclu.

Pentru a calcula in general $D[i]$ trebuie sa gasim o formula de recurenta. Pentru aceasta, sa consideram un $i$ fixat:

putem sa ne fixam de la inceput un nod dintre aceastea $i$ si sa stabilim in ce ciclu il vom pune; inainte de toate putem fixa dimensiunea ciclului care contine acest nod (poate fi orice numar intre $3$ si $i$ ) pe care o notam $k$
in cate moduri putem alege acum cele $k-1$ noduri care vor fi adaugate in acelasi ciclu cu nodul fixat? Pot fi oricare dintre celelalte $i-1$ noduri, deci in total $C_{i-1}^{k-1}$ posibilitati
acum avem fixate cele $k$ noduri ale ciclului ce contine nodul nostru, in cate moduri putem sa le aranjam pe ciclu? Am fi tentati sa spunem $k!$ (numarul de permutari de dimensiune $k$ ), insa lucram pe un ciclu, deci permutari de genul $(1,3,4,2)$ , $(3,4,2,1)$ , $(4,2,1,3)$ si $(2,1,3,4)$ corespund aceluiasi ciclu. Observam de fapt ca pentru orice ciclu ii putem gasi in mod unic $k$ permutari de lungime $k$ , deci numarul total de aranjari ale nodurilor pe ciclu este $(k-1)!$
am fixat tot ce tinea de ciclul ce contine nodul initial, ce facem cu resul de $i-k$ noduri? In cate moduri putem sa le organizam pe ele acum sub forma de cicluri? Aceste posibilitati le avem numarate in $D[i - k]$ .

Obtinem deci recurenta:
$D[i] = \sum_{k=3}^{i} C_{i-1}^{k-1} \cdot (k-1)! \cdot D[i-k]$

Pe care o putem implementa astfel:

// calculam dinainte Fact[i] = i!
// si C[i][j] = combinari de i luate cate j (triunghiul lui Pascal)
D[0] = 1; D[1] = 0; D[2] = 0; D[3] = 1;
for (int i = 4; i <= N; i++) {
	D[i] = 0;
	for (int k = 3; k <= i; k++) {
		D[i] += C[i-1][k-1] * Fact[k-1] * D[i-k];
	}
}

Pentru a lua $100$ de puncte, calculele de mai sus trebuie facute cu ajutorul operatiilor pe numere mari.