De ce contează?
Gândește-te la ceasul de perete. Adaugi 5 ore peste ora 10 și nu ajungi la ora 15 — ajungi la ora 3, fiindcă ceasul „resetează" la 12. Ora exactă pe care ai parcurs-o nu te interesează; te interesează doar unde se oprește acul. La problemele de numărare facem exact la fel: răspunsul real are sute de cifre și n-am unde să-l ținem, dar restul lui față de un număr fixat încape ușor — și e tot ce ni se cere.
Ideea-cheie
La combinatorică, răspunsurile cresc exploziv. Numărul de aranjări a 25 de elemente
este , un număr cu 26 de cifre. Numărul de submulțimi ale unui set de 100 de
elemente este , un număr cu 31 de cifre. Cel mai mare întreg pe care îl ții
într-un long long are doar vreo 19 cifre — deci aceste răspunsuri nu încap,
oricât de mare ai alege tipul de date.
De aceea enunțurile nu cer numărul în sine, ci cer „rezultatul modulo 1000000007".
Adică: nu ne da numărul uriaș, dă-ne doar restul lui la împărțirea cu acel prim.
Restul are mereu cel mult 9 cifre, deci încape lejer.
Trucul care face totul să funcționeze: nu calculezi întâi numărul uriaș și abia apoi îi iei restul (numărul uriaș nici n-ai unde să-l ții). Iei restul la fiecare pas. Restul se păstrează prin adunare, scădere și înmulțire — deci poți lucra tot timpul cu numere mici și răspunsul final iese corect.
Nu poți păstra numărul uriaș, dar nu ai nevoie de el — restul lui față de m îți
ajunge. Și acel rest „se poartă bine": dacă reduci modulo m după fiecare adunare,
scădere sau înmulțire, obții același rest ca și cum ai fi calculat numărul întreg și
abia la final i-ai fi luat restul. Lucrezi mereu cu numere mici, fără să pierzi nimic.