De ce contează?
Nu poți căra un munte întreg în rucsac — dar poți căra restul lui care încape: o pietricică reprezentativă. La fel cu numerele combinatoriale: răspunsul real e gigantic, imposibil de purtat. Lucrând „modulo”, cari doar restul mic — și totuși e suficient ca să dovedești că ai răspunsul corect.
De ce explodează numerele combinatoriale
Răspunsurile la problemele de numărare cresc îngrozitor de repede:
n!(factorial):20!are deja 19 cifre și depășeștelong long.25!e astronomic.2^n(submulțimi): dublul la fiecare pas —2^63iese dinlong long.- numerele Catalan, combinări
C(n, k)mari: cresc exponențial.
Un long long ține valori până la aproximativ 9.2 * 10^18. Pentru n de ordinul
sutelor sau miilor, rezultatul are sute de cifre — niciun tip întreg nu îl ține.
De aici problema: dacă lași numărul să crească liber, ai overflow și obții
gunoi, nu răspunsul.
Ce e modulo și ce păstrează
a mod p este restul împărțirii lui a la p. Pentru p = 1000000007, orice
rest e între 0 și p - 1, deci mereu mic — încape lejer în long long.
Magia: pentru +, − și ×, restul rezultatului depinde doar de resturile
operanzilor. Deci poți lucra tot timpul cu numere mici și totuși obții același rest
final ca și cum ai fi calculat valoarea uriașă întreagă. Pierzi cifrele exacte, dar
păstrezi o amprentă verificabilă a răspunsului.
Tabel: operație → cum o faci modulo
| Operație | Forma modulo | Ce ai grijă |
|---|---|---|
adunare a + b | (a + b) % p | rezultat mic, sigur |
scădere a - b | ((a - b) % p + p) % p | normalizezi: scăderea poate da negativ |
înmulțire a * b | (a * b) % p | folosește long long, altfel a*b face overflow |
împărțire a / b | a * inv(b) % p | nu împarți direct — folosești inversul modular |
Primele trei merg „natural”. A patra e capcana capitolului: împărțirea nu comută cu modulo, așa că o înlocuiești cu înmulțire cu inversul modular al numitorului (vezi lecția invers-modular).
Când și cum recunoști în enunț
Caută în cerință formulări de tipul:
- „afișați rezultatul modulo 1000000007” (sau
10^9 + 7), - „răspunsul poate fi foarte mare, dați restul împărțirii la ...”,
- „numărul de moduri ... modulo un număr prim”.
Numărul 1000000007 e ales pentru că e prim și aproape de 10^9 (deci o
înmulțire de două resturi încape în long long). Fiind prim, ai garanția că
inversul modular există pentru orice numitor nenul (Fermat).
Regula de aur: aplici modulo la fiecare pas, nu la final. Dacă lași
produsul să crească și pui % p abia la sfârșit, numărul a depășit deja long long
în pașii intermediari — restul final e deja corupt.
La înmulțire, chiar dacă a și b sunt deja mai mici decât p ≈ 10^9, produsul
a * b ajunge la ~10^18 — aproape de limita lui long long. De aceea calculul
trebuie făcut pe long long, nu pe int. Iar la împărțire nu te poți baza pe /:
ai nevoie de inversul modular, singura cale corectă modulo prim.
Greșeli reale de decizie:
- Modulo doar la final: lași
n!sau produsul să crească și pui% pla sfârșit. Numărul a explodat deja în pașii intermediari — restul e gunoi. Pune% pdupă fiecare operație. - Împărțire directă modulo: scrii
(a / b) % pcrezând că e ca la+și×. Împărțirea nu comută cu modulo — ai nevoie de inversul modular al luib. - Uiți
long longla înmulțire: înmulțești peintșia * bface overflow înainte de% p. Produsul a două resturi cerelong long. - Modulo negativ nenormalizat: după o scădere
a - bpoți obține un rest negativ. Fără(... + p) % prămâi cu o valoare negativă care strică tot lanțul.
Recapitulare
- Numerele combinatoriale (
n!,2^n, Catalan) explodează — modulo păstrează un rest mic, dar verificabil; de aceea enunțurile cer „modulo 1000000007”. +,−,×merg direct modulo (culong longla×și normalizare(... + p) % pla−);÷cere invers modular, fiindcăpe prim.- Aplici modulo la fiecare pas, niciodată doar la final — altfel ai overflow înainte să apuci să iei restul.