Problemi 096

Kërkesa

Jepet një numër n. Gjeni mbetjen e pjesëtimit të shumës \(1! + 2! + ... + n!\) me \(10^9 + 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 \(L_x + L_{x+1} + ... + L_{y-1} + L_y = (L_0 + L_1 + ... + L_{x-1}) + (L_{y+1} + L_{y+2} + ... + L_{N-1})\).

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 < N-1\). Gjithashtu \(3 <= N <= 10^5\) dhe \(1 <= L_i <= 10^5\).

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