Fişierul intrare/ieşire:shoturi.in, shoturi.outSursăAutumn WarmUp 2019
AutorTinca MateiAdăugată deTincaMateiTinca Matei TincaMatei
Timp execuţie pe test2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Shoturi

De obicei, dacă ai două lucruri bune pe care le combini, poate să iasă un lucru şi mai bun! În problema de faţă vom vedea anumite lucruri care nu respectă această regulă.

Printre tinerii din ziua de azi circulă un nou joc: ei au pe masă N substanţe interzise sucuri numerotate de la 1 la N, iar în mijloc au un pahar cu o capacitate de K shoturi, iniţial gol. Fiecare suc este dăunător pentru organism, de aceea pentru fiecare suc i (1 ≤ i) cunoaştem coeficientul hazard[i]. Jocul decurge astfel: amestecul din pahar are iniţial potenţa 1; pentru fiecare suc i (1 ≤ N) putem să alegem un număr de shoturi x[i] natural; dacă x[i] este 0, atunci potenţa amestecului nu se modifică; în caz contrar, acesta se înmulţeşte cu x[i] * hazard[i]. Când paharul se umple, unul din tineri care e la rând bea amestecul acela. Pentru a demonstra că acest joc este periculos, vrem să aflăm suma potenţelor tuturor amestecurilor posibile.

Pe scurt, vrem să aflăm suma din f(x[1], x[2], ..., x[N]) = \displaystyle\prod_{i=1; x[i] \neq 0}^{N} x[i] * hazard[i] pentru toate configuraţiile posibile ale lui x, astfel încât x[1] + x[2] + ... + x[N] = K.

Deoarece jocul poate deveni foarte periculos, iar tinerii de la informatică sunt periculoşi, se cere această sumă modulo 269.696.969.

Date de intrare

Fişierul de intrare shoturi.in va conţine pe prima linie numerele N şi K cu semnificaţia din enunţ.
Pe a doua linie se vor afla N numere separate prin câte un spaţiu reprezentând coeficientul hazard[i] al fiecărui suc.

Date de ieşire

Fişierul de ieşire shoturi.out va conţine pe prima linie suma cerută modulo 269.696.969.

Restricţii

  • 1 ≤ N, K ≤ 5.000
  • 1 ≤ hazard[i] ≤ 100.000.000
  • Pentru 10 puncte, N, K ≤ 12
  • Pentru alte 40 de puncte, N, K ≤ 300
  • Pentru alte 30 de puncte, N, K ≤ 2.000

Exemplu

shoturi.inshoturi.out
2 3
2 3
39
10 100
1 2 3 4 5 6 7 8 9 10
261463837
30 5000
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
145836083

Explicaţie

Dacă turnăm suc doar din tipul 1, atunci vom avea x = {3, 0}, deci f({3, 0}) = x[1] * hazard[1] = 3 * 2 = 6.
Dacă turnăm suc doar din tipul 2, atunci vom avea x = {0, 3}, deci f({0, 3}) = x[2] * hazard[2] = 3 * 3 = 9.
Dacă turnăm suc din ambele tipuri, atunci x va avea mai multe soluţii:

  • x = {1, 2}, deci f({1, 2}) = (x[1] * hazard[1]) * (x[2] * hazard[2]) = (1 * 2) * (2 * 3) = 12.
  • x = {2, 1}, deci f({2, 1}) = (x[1] * hazard[1]) * (x[2] * hazard[2]) = (2 * 2) * (1 * 3) = 12.

Deci răspunsul va fi f({0, 3}) + f({3, 0}) + f({1, 2}) + f({2, 1}) = 6 + 9 + 12 + 12 = 39.

Pentru al doilea şi al treilea exemplu, comisia nu mai ţine minte cât de nebun a fost jocul, în schimb a aflat a doua zi, aşa că va trebui să credeţi pe cuvânt sursele externe.

Observaţie: al treilea exemplu este pus pe 3 rânduri din motive de formatare.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?