Za rešavanje ovog zadatka koristim kumulativne tabele + Binary Indexed Tree, kao i modularnu aritmetiku (množenje i deljenje). Samo dva testa su OK, kod većine T.L.E, a kod nekih W.A.
Help me.
Da li je ova ideja vodi ka rešenju ili ne, ili neka druga ideja? Ako je ko voljan da pogleda post:
http://www.z-trening.com/new/www/html/submit.php?subm_stat=1&submit=7100053303
Ideja je ok... Kod ne mogu sad da pogledam
a da se pokušaš rješit big numova.možda je to greška.
btw. nisam rješio zadatak ali kada sam ga prvi put pogledo pomislio sam na big num
Nemam to u kodu.
@Matteo, mislim da nisi pogledao moj zadnji post za tvoje pitanje 'cifre'.
Ne razumem bas najbolje neke funkcije, tj. funkciju Mod_1.
Inace
( A / B ) mod m = ( ( A mod m ) * ( B^( m - 2 ) mod m ) ) mod m.
Znaci za polje [i,j], resenje je
[i,j]*[i-1,j-1] / [i-1,j] / [i,j-1].
Sad samo to upakujes u ovo modularno deljenje (trebace ti brz algoritam za stepenovanje na 10005) i trebalo bi da radi.
Hvala ti. Tačno si pogodio sta me muči. Inače, Mod_1 je inverzija po modulu (tj. ako je a*b=1 mod m, onda su oni inverzni po modulu m). Čak je na par mojih test primera sve i bilo ok. Ali kada sam postovao kod i dobajao W.A., pretpostavio sam da to nije u redu, ali ... Što se tiče stepenovanja svestan sam toga, ali sam tako uradio samo da ne bi dobija W.A.
Ja nisam znao za ovo pravilo za modularno deljenje i mislim da će ti mnogi biti zahvalni za tvoj odgovor (ako ga pročitaju). Pozdrav.
vec je napisano vise puta, no prije da te upozorim da to za modularno dijeljenje vrijedi samo kad je m prost.
nesto generalnije je pronalazenje modularnog inverza prosirenim euklidovim algoritmom, ono vrijedi ukoliko su B i m relativno prosti.
to sam i pokušavao,preko modularnog inverza (ali ne euklidovim algoritmom) ali sam dobija w.a. Hvala vam, sad znam u kom pravcu da dalje tražim rešenje.
