2421 - CalculSume

Cerința

Cu n numere naturale, a1,a2,…,an , se pot calcula următoarele sume: S1=a1+a2+…+an

S2=a1⋅a2+a1⋅a3+…+an−1⋅an

S3=a1⋅a2⋅a3+a1⋅a2⋅a4+…+an−2⋅an−1⋅an

... Sn=a1⋅a2⋅…⋅an .

Se dau două numere n

și k
și apoi n numere naturale a1,a2,…,an

. Se cere să se calculeze suma Sk .

Date de intrare

Fișierul de intrare calculsume.in conține pe prima linie două numere n și k separate printr-un spațiu, urmate, pe a doua linie de n numere naturale separate de asemenea, prin spații.

Date de ieșire

Fișierul de ieșire calculsume.out va conține rezultatul cerut.

Restricții și precizări

1 ≤ k ≤ n ≤ 100 numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 101 pentru că sumele cerute pot avea valori foarte mari, se cere să se afișeze restul împărțirii acestora la 9973 Exemplul 1: calculsume.in

3 1 1 2 3 calculsume.out

6 Exemplul 2: calculsume.in

3 2 1 2 3 calculsume.out

11 Exemplul 3: calculsume.in

3 3 1 2 3 calculsume.out

6

Explicație

Cele 3 exemple citesc câte un set de date de intrare, pentru fiecare se va afișa rezultatul cerut.

S 1 = 1 + 2 + 3, deci suma S1 este 6

S 2 =1*2+1*3+2*3, deci suma S2 este 11

S 3 =1*2*3, deci suma S3 este 6.

Rezolvare

MOD = 9973

def calculeaza_suma_k(n, k, numere):

   sume = [0] * (k + 1)
   for i in range(1, n + 1):
       for j in range(k, 0, -1):
           sume[j] = (sume[j] + numere[i - 1] * sume[j - 1]) % MOD
   
   return sume[k]

if __name__ == "__main__":

   with open("calculsume.in", "r") as f:
       n, k = map(int, f.readline().split())
       numere = list(map(int, f.readline().split()))
   rezultat = calculeaza_suma_k(n, k, numere)
   with open("calculsume.out", "w") as g:
       g.write(str(rezultat) + "\n")