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 1

import sys
sys.setrecursionlimit(100000)

def factorial(n):
    return 1 if n==1 else n*factorial(n-1)

def factorial_sum(n):
    return 1 if n==1 else factorial(n) + factorial_sum(n - 1)

for _ in range(int(input())):
    n = int(input())
    print(factorial_sum(n) % 1000000007)

Sqarime

Kjo zgjidhje është e thjeshtë po tepër jo-efiçente. Ajo kalon vetëm testin e parë (n=1000).

Zgjidhja 2

import sys
sys.setrecursionlimit(100000)

hash_factorials = {1:1, 2:2, 3:6}
hash_factorial_sums = {1:1}

def factorial(n):
    f = hash_factorials.get(n, False)
    if f: return f

    f = n * factorial(n - 1)
    f %= 1000000007
    hash_factorials[n] = f
    return f

def factorial_sum(n):
    s = hash_factorial_sums.get(n, False)
    if s: return s

    s = factorial(n) + factorial_sum(n - 1)
    s %= 1000000007
    hash_factorial_sums[n] = s
    return s

for _ in range(int(input())):
    n = int(input())
    print(factorial_sum(n))

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

n = 10**5
m = 10**9 + 7
sums = [0 for i in range(n+1)]

f = 1
s = 0
for i in range(1, n+1):
    f *= i
    f %= m
    s += f
    s %= m
    sums[i] = s

for _ in range(int(input())):
    n = int(input())
    print(sums[n])

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