| Fişierul intrare/ieşire: | nane.in, nane.out | Sursă | FMI No Stress 9 Warmup |
| Autor | Mihai-Dragos Preda, Usurelu Florian Robert | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 4096 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | nane.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)
