Jap2

Ştim că putem afla puterea la care apare numărul prim P în N! folosind formula [^N/_P] + [^N/_P²] + [^N/_P³] + ..., unde [x] reprezintă partea întreagă a lui x. Pentru un query A, B putem determina puterea la care apare P în A!, B! şi A-B! şi deci putem afla puterea la care apare P în Combinări(A, B).

În cazul în care C(A, B) este divizibil cu P, răspunsul este, evident, 0. În cazul în care C(A, B) nu este divizibil, vom încerca să determinăm rapid valoarea lui N! ignorând toţi factorii lui P.

Să luăm un exemplu pentru P = 3 şi să vedem cum arată valorile din 2!, 8! şi 26!. Vom ignora toţi factorii lui 3, deci 3 devine 1, 6 devine 2, 9 devine 1, 12 devine 4 modulo 3 = 1, etc.

Pentru 2 produsul este egal cu 1*2.
Pentru 8 produsul este egal cu (1*2)*1*(1*2)*2*(1*2).
Pentru 26 produsul este egal cu: (1*2*1*1*2*2*1*2)*1*(1*2*1*1*2*2*1*2)*2*(1*2*1*1*2*2*1*2).

Putem observa că pentru numere de forma P^k-1, cu k număr natural, valoarea lui P^k-1-1 se repetă de P ori şi în plus pe poziţiile de forma l * P^k-1 din şir se află numerele de la 1 la P-1.

De aici, reiese o idee de rezolvare: Când vrem sa calculăm N! factorial încercăm să-l reducem la probleme mai mici folosindu-ne de faptul că produsurile de mai sus se repetă.

Vom precalcula toate valorile lui x!, cu x între 1 şi P-1 şi toate valorile factorialelor pentru numere de forma P^k-1 (se poate găsi uşor relaţie de recurenţă între P^k-1-1 şi P^k-1).

Pentru a calcula N!, ne vom uita la cel mai mare număr de forma P^k-1, care e mai mic strict ca N. Putem determina de câte ori se repetă produsul de lungime P^k-1 în desfăşurarea lui N! printr-o împărţire şi câti din factorii 1, 2, ..., P-1 din afara produsurilor există. Dacă N nu este la rândul lui de forma P^k+1-1, atunci ultimul dintre produsele de forma P^k-1 va fi incomplet şi va trebui să-l calculăm recursiv în acelaşi mod descris. Adâncimea maximă pe care o avea funcţia va fi egală cu O(log_P N) şi pentru că vom avea nevoie de o funcţie care să ridice o valoare la orice putere în timp logaritmic complexitatea finală va fi O(log_P N * log₂ P) pe test.

Având calculate factorialele A!, B! şi A-B! simplificate putem calcula combinările folosind conceptul de invers modular, care ne permite să simulăm împărţirea pe numere naturale in aritmetica modulară.

În timpul concursului am aflat din sursele concurenţilor de existenţa Teoremei lui Lucas care rezolvă aceeasi problemă, spre dezamăgirea autorului. :( Soluţia oficială prezentată mai sus poate fi extinsă însă pentru calcularea Aranjamentelor sau doar a Factorialului.

Tot prin precaluclarea factorialelor pana la puterea P se puteau obtine 70-80p. Cand avem de calculat un factorial N! il vom il vom afla in timp logaritmic calculandul astfel: N = pwr( Fact [ P ] , X ) + pwr ( Fact [ R ] , Y ) + ... , unde X este prima putere a lui P mai mica decat N , unde R este N - P^X , s.a.m.d. si unde pwr reprezinta ridicarea la putere , fiecare ridicare la putere putandu-se calucula in timp logaritmic.

O abordare de 50p ar fi fost preprocesarea factorialelor pana la A.