Fişierul intrare/ieşire:nane.in, nane.outSursăFMI No Stress 9 Warmup
AutorMihai-Dragos Preda, Usurelu Florian RobertAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Nane

Nane de pe Jiu, mare algoritmician fiind, va provoaca sa rezolvati o problema prea usoara pentru el. Nane va da N numere pozitive si un numar K. Fie Sp suma OR (operatia pe biti) a numerelor unei subsecvente. Numim o subsecventa speciala daca Sp-ul subsecventei are in reprezentarea sa binara maxim K biti de 1. Nane va cere numarul de subsecvente speciale.

Doua subsecvente sunt diferite daca cel putin o pozitie din una nu se regaseste in celalata.

Dovediti-i lui Nane ca sunteti priceputi in ale algoritmicii si calculati numarul cerut!

Date de intrare

Fişierul de intrare nane.in va contine pe prima linie 2 numere N si K, iar pe a 2-a linie N numere.

Date de ieşire

În fişierul de ieşire nane.out se va afla pe prima linie un singur numar Nr, reprezentand numarul cerut de Nane.

Restricţii

  • 1 ≤ N ≤ 100.000 ; 1 ≤ K ≤ 30
  • Pentru 20 puncte 1 ≤ N ≤ 50
  • Pentru alte 30 puncte 1 ≤ N ≤ 1.000
  • Toate cele N numere vor fi naturale si se pot reprezenta pe 30 de biti

Exemplu

nane.innane.out
5 2
2 14 3 2 10
6
7 3
13 12 14 9 1 11 11
15

Explicaţie

  • Exemplu: subsecventa 2 6 are suma OR 6; 6 in binar este 110 (2 biti de 1). Aceasta subsecventa va fi numarata daca K>=2.

In primul exemplu, subsecventele sunt: (1), (3), (3,4), (4), (4,5) si (5)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?