Problemi 154

Kërkesa

Jepet një listë L që ka numrat nga 1 deri në N. Në këtë listë bëhet ky veprim: Merren dy elementë X dhe Y të listës, fshihen nga lista, dhe pastaj shtohet në listë numri X + Y + X*Y. Nëse ky veprim bëhet N-1 herë në listë do ngelet vetëm 1 element. Sa është vlera më e madhe që mund të ketë ky element? Meqë rezultati mund të jetë një numër shumë i madh, jepni si përgjigje vetëm mbetjen e pjesëtimit të tij me \(10^9 + 7\).

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

Shembull

$ cat input.txt
2
1
2

$ python3 prog.py < input.txt
1
5

Zgjidhja

P = 10**9 + 7
N = 10**6
R = [0 for i in range(N+1)]
R[1] = 1
for i in range(2, N+1):
    R[i] = (R[i-1] + i + i*R[i-1]) % P 
    
for _ in range(int(input())):
    print(R[int(input())])

Sqarime

Po ta bëjmë atë veprim në një listë me tre numra [x1, x2, x3] do shikojmë që rezultati është gjithmonë njëlloj dhe i pavarur nga radha e veprimit. Kjo mund të përgjithësohet edhe për një listë me më shumë numra. Kjo na lejon që ti llogarisim paraprakisht në mënyrë efiçente të gjitha rezultatet e mundshme.

Gjithashtu mund të vihet re edhe se: (X + Y + XY) % P = X % P + Y % P + (XY) % P. Kjo na lejon që të punojmë vetëm dhe mbetjet e veprimeve dhe jo me numrat e plotë, që janë jashtëzakonisht të mëdhenj, dhe kjo e bën programin edhe më efiçent.