Fişierul intrare/ieşire:media.in, media.outSursăInfoPro, Etapa 3, Grupa B
AutorAlexandru PetrescuAdăugată demihai50000Mihai-Cristian Popescu mihai50000
Timp execuţie pe test0.2 secLimită de memorie64000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Media

Fie V un şir de numere întregi, nenegative, de lungime N.

Cerinţă

Ştiindu-se şirul V şi numărul natural M, să se calculeze numărul subsecvenţelor cu proprietatea că media geometrică a elementelor din subsecvenţă este egală cu M.
Prin subsecvenţă a unui şir dat se înţelege o succesiune de unul sau mai mulţi termeni din şir aflaţi pe poziţii consecutive.

Date de intrare

Fişierul de intrare media.in conţine pe prima linie numerele N şi M, iar pe următoarea linie N numere întregi, nenegative.

Date de ieşire

Fişierul de ieşire media.out va conţine un singur număr care reprezintă valoarea cerută.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 0 ≤ V[i] ≤ 109
  • 2 ≤ M ≤ 109
  • Media geometrică a numerelor a_1, a_2, ..., a_K \geq 0 este \sqrt[K]{a_1 a_2 ... a_K}.
  • Punctarea se va face separat, testele fiind independente unul de altul. Punctajele pe subtaskuri diferă de cele din concurs.
  • Primul test respectă următoarea restricţie: 1 ≤ N ≤ 50.
  • Testele 2-6 respectă următoarea restricţie: M şi elementele vectorului V sunt puteri ale lui 2.
  • Testele 7-10 nu au restricţii suplimentare.

Exemplu

media.inmedia.out
5 4
1 2 4 8 4
4

Explicaţie

Subsecvenţele căutate sunt: [4], [4], [2, 4, 8], [2, 4, 8, 4]

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?