Fişierul intrare/ieşire:supersuma.in, supersuma.outSursăIIOT 2019-20 Runda 3
AutorAlexandru PetrescuAdăugată deBodo171Bogdan Pop Bodo171
Timp execuţie pe test0.1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Supersuma

Se considera un sir A de N numere intregi. Operatia Verde aplicata sirului A se face in doi pasi:

  • Pasul 1. Se construieste un sir de numere intregi B. Initial, sirul e vid. Se considera toate submultimile lui A, inclusiv multimea vida, se calculeaza suma fiecareia, si se adauga numarele respective in sirul B.
  • Pasul 2. Se inlocuieste A cu B. Apoi, B devine din nou vid.

Se cere suma modulo M a numerelor din sirul obtinut dupa ce operatia Verde a fost aplicata de K ori sirului A.

Date de intrare

Fişierul de intrare supersuma.in contine, pe prima linie, numerele N, K si M. Pe urmatoarea linie se afla numerele din care e format sirul A.

Date de ieşire

În fişierul de ieşire supersuma.out se va afla un singur numar, si anume cel cerut.

Restricţii

  • 1 ≤ N ≤ 50
  • 1 ≤ K ≤ 109
  • 1 ≤ M ≤ 109 + 7
  • 0 ≤ Ai ≤ M
  • M este impar
  • Pentru 20 de puncte, M = 109+7, k = 1
  • Pentru alte 10 puncte, M = 109+7, k = 2
  • Pentru alte 10 puncte, k = 2
  • Pentru alte 20 de puncte, M<=500, k<=50.000
  • Pentru alte 20 de puncte, M=109+7, k<=50.000
  • Pentru restul de 20 de puncte, M<=109+7, k<=109

Exemplu

supersuma.insupersuma.out
3 1 9999
1 2 3
24
3 4 29
0 23 0
26
4 50000 49999
2 0 2 3
43310

Explicaţie

In primul exemplu, sirul A dupa operatia Verde este 0 1 2 3 3 4 5 6.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?