957 Jap2

[•bogdan2412]

Aici puteti discuta despre problema Jap2.

[•DraStiK]

As avea si eu o intrebare: Chiar daca am citit solutia oficiala si acolo este explicat altfel, as dori sa intreb de ce nu merge calculat

C (a,b) % p folosind invers modular, adica C (a,b)%p=(a! * b!^(p-2) * (a-b)!^(p-2))%p.

Multumesc anticipat. 

[•pauldb]

Pentru ca produsul ar putea contine un multiplu de p si ar da 0. In realitate, daca puterile lui p se simplifica, raspunsul e diferit de 0.

[•CezarMocan]

As avea si eu o intrebare: Chiar daca am citit solutia oficiala si acolo este explicat altfel, as dori sa intreb de ce nu merge calculat

C (a,b) % p folosind invers modular, adica C (a,b)%p=(a! * b!^(p-2) * (a-b)!^(p-2))%p.

Multumesc anticipat. 

Se poate, doar ca am impresia ca iti creste complexitatea (spun asta pentru ca iau TLE pe 7 teste cu aceasta solutie). Pentru ca produsul sa dea restul bun si nu 0, trebuie sa scoti toti factorii de P din factoriale. Sa il luam ca exemplu pe B!. Cel mai simplu e sa scoti toate numerele divizibile cu P din produsul 1*2*3*...*B, si o sa iti ramana un B!_prim (egal cu B! / produsul_numerelor_divizible_cu_P). Dar tu ai scos toate numerele divizibile cu P, nu doar factorii de P. Si numerele astea divizibile cu P au forma 1*P, 2*P, ... K*P. Ceea ce inseamna ca pentru ca produsul sa fie valid ar trebui sa il inmultesti pe B!_prim cu K!. Doar ca si in K! o sa iti apara factori de P . Tot repeti procedeul pana cand ajungi sa nu mai ai factori de P. Asa ajungi sa obtii restul bun.
Sper ca am fost destul de explicit.

[•popoiu.george]

Recurenta din solutie este cumva P^k-1 = ( P^k-1-1 ) * (P-1)! , toate luate modulo P ?

P.S. : Topicul nu este legat de problema.

LE : Imi explicati va rog cum sa precalculez valorile de forma P^k-1 ? Ca nu reusesc sa ma prind.

[•danalex97]

Eu calculez A! in felul urmator si nu stiu daca e corect. Fac vectorul F [ i ] = i! , unde i<P. Apoi folosesc o formula , considerand ca divizorii lui P se reduc.
Formula arata cam asa:

Cod:

Fact(A) = ( F [ P-1 ] ^ (A / P) ) * ( F [ P-1 ] ^ (A / ( P * ( P-1 ) ))  ) * F [ A%P ] * F [ A% ( P * (P-1) ) ] 

Evident , ce e mai sus e totul %P.
De exemplu pentru factorial 13 si P=5 ma gandesc in felul urmator:
1 * 2 * 3 * 4 * 1 * 1 * 2 * 3 * 4 * 2 * 1 * 2 * 3

Adica am ( 1*2*3*4 ) ^2 = F[4] ^2 = ( F [ P-1 ] ^ ( A / P ) ) , 1 * 2 = F[2] =F[ A%( P * (P-1) ) ] si 1 * 2 * 3 = F[3] = F [ A%P ]

Nu reusesc sa imi dau seama de greseala. Daca cineva are o idee asemenatoare sa imi spuna.
In problema toate cele 3 factoriale le calculez asa si apoi fac invers modular cu Fact(A) / Fact( B ) / Fact( A-B ) .

Multumesc anticipat. 

[•SebiSebi]

Salut!
Am rezolvat problema astfel :
 - am determinat puterea la care apare P in N! in O ( log _P N ) , folosind o formula;
 - am gasit , daca mai este cazul , N! % P ignorand toti factorii lui P din N! , in O (log _P N * log ₂ P ).
  Primul logaritm vine de la descompunerea lui N! in factoriale mai mici care se repeta din P in P , iar al doilea de la ridicare la putere. Am incercat si ridicarea la putere pe biti insa nu reusesc sa scap de TLE pe 11 teste. Operatiile necesare le fac pe long long , iar operatia rest nu imi dau seama cum s-o inlocuiesc cu scadere.

Ce as mai putea optimiza pentru ca sursa sa intre in timp? ( am citit solutia oficiala si are aceasi complexitate , l-am rugat pe Popa Mihai sa trimita sursa lui care lua 100 si acum primeste 70).
Multumesc anticipat!

[•klamathix]

Am modificat limita si Mihai ia acum 100, tu iei 60. Avand in vedere ca exista acum sursa de 100 si timpii lui maximi sunt cu 200 ms mai mici decat limita, am sa te rog sa mai incerci sa optimizezi putin. Daca totusi nu iese, sa ma anunti.

[•AlexandruValeanu]

Salut!
Am incercat o rezolvare cu teorema lui Lucas astfel: am descompus A, B in baza P si am facut produs de combinari ca in teorema. Avand precalculate factorialele si inversele modulara pana la P in O(P log P) am raspuns pe query in O(1) + descompunerea. Se poate lua 100p cu o rezolvare ca aceasta deoarece eu iau pe testele 14-20 TLE ?

[•andreipirjol]

Misto problema de mate. Dupa ce o fac vreau cadoul pe facebook pls