Problemi 096

Kërkesa

Jepet një numër n. Gjeni mbetjen e pjesëtimit të shumës 1!+2!+...+n! me 109+7 (i cili është numër i thjeshtë).

Referenca: https://www.codechef.com/DARG2019/problems/SUMMOD

Shembull

$ cat input.txt
3
1000
10000
100000

$ python3 prog.py < input.txt
980630010
396626132
789934569

Zgjidhja 2

Sqarime

Kjo zgjidhje është më e shpejtë se e para sepse nqs është gjetur njëherë faktoriali i një numri, ai mbahet shënim dhe nuk rillogaritet.

Gjithashtu mbahen shënim vetëm mbetjet përkatëse, meqenëse (a * b) % n == ((a % n) * (b % n)) % n dhe (a + b) % n == ((a % n) + (b % n)) % n.

Edhe pse është më e shpejtë se e para, kjo zgjidhje nuk e kalon testin e tretë.

Zgjidhja 3

Sqarime

Mund ti llogarisim paraprakisht të gjitha shumat, në mënyrë hap-pas-hapi, dhe rezultatet ti mbajmë shënim në një listë. Pastaj për çdo n që të na jepet ne e kemi përgjigjen gati (te lista sums).

Kjo zgjidhje është mjaft e shpejtë dhe e kalon edhe testin e tretë.

Detyra

Një klasë ka N nxënës dhe pikët e secilit prej tyre na jepen në një listë L. Gjeni të gjitha prerjet e mundshme P=(x,y) që mund ti bëhen kësaj liste, të tilla që shuma e pikëve brenda prerjes të jetë e barabartë me shumën e pikëve jashtë prerjes. Dmth Lx+Lx+1+...+Ly1+Ly=(L0+L1+...+Lx1)+(Ly+1+Ly+2+...+LN1).

Nëse nuk ka asnjë prerje të tillë printoni -1, përndryshe printoni numrin e prerjeve dhe shumën e indekseve x dhe y për të gjitha prerjet. Këto indekse janë me bazë 0, dhe 0<x<=y<N1. Gjithashtu 3<=N<=105 dhe 1<=Li<=105.

Referenca: https://www.codechef.com/problems/EQSBAR

Shembull

$ cat input.txt
2
10
7 8 12 8 13 9 5 7 12 3
5
32 36 34 20 28

$ python3 prog.py < input.txt
2 17
-1