Rezolvare PBinfo #3758

Se dau numerele naturale n și k, precum și un șir a[1], a[2] ,…, a[n] de numere naturale nenule. Din șir de poate elimina o singură secvență (eventual vidă) a[i], a[i+1], …, a[j] astfel că în șir rămân elementele a[1], a[2], …, a[i-1], a[j+1], …, a[n].

De exemplu, din șirul a=(1,2,3,4,5,7) se poate elimina secvența 3,4,5 și rămâne 1,2,7; sau se poate elimina secvența vidă și rămâne șirul inițial 1,2,3,4,5,7; sau se poate elimina 1,2,3,4 și rămâne șirul 5,7.

După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația & pe biți asupra lor rezultatul este un număr care are cel puțin k biți de 1 în baza 2. De exemplu, dacă a=(1,2,3,4,5,7) și k=2, atunci prin eliminarea secvenței 1,2,3,4 rămân elementele 5,7, iar 5 & 7 = 5, care are 2 biți de 1 în baza 2. Dar dacă se elimină secvența 3,4,5 atunci rămân elementele 1,2,7, iar 1 & 2 & 7 = 0, deci nu este șir inno.

Cerința

Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.

Date de intrare

Fișierul de intrare inno.in conține pe prima linie numerele naturale n și k. Pe linia a doua se află n numere naturale reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire inno.out va conține pe prima linie un singur număr natural reprezentând numărul de moduri de a elimina o secvență astfel încât șirul rămas să fie inno.

Restricții și precizări

• 3 ≤ n ≤ 200.000;
• 1 ≤ k ≤ 29;
• 0 ≤ a[i] ≤ 231 - 1;
• & este operatorul de conjuncție pe biți. Dacă x și y sunt valori binare, atunci expresia x & y este egală cu 1 dacă și numai dacă x = 1 și y = 1. Deci 1 & 1 = 1, 0 & 1 = 0, 1 & 0 = 0, 0 & 0 = 0. Dacă a și b sunt numere naturale, atunci expresia a & b se efectuează la nivelul reprezentării în baza 2. De exemplu, dacă a = 12 și b = 20, atunci a & b = 12 & 20 = 01100(2) & 10100(2) = 00100(2) = 4(10);

Exemplul 1:

inno.in

4 2
10 7 5 15

inno.out

5

Explicație

Modalitățile sunt:
- se elimină 10 și rămâne șirul 7 5 15, iar 7 & 5 & 15 = 5, care are 2 biți de 1
- se elimină 10 7 și rămâne șirul 5 15, iar 5 & 15 = 5, care are 2 biți de 1
- se elimină 10 7 5 și rămâne șirul 15, iar 15 are 4 biți de 1
- se elimină 7 5 și rămâne șirul 10 15, iar 10 & 15 = 10 are 2 biți de 1
- se elimină 7 5 15 și rămâne șirul 10, iar 10 are 2 biți de 1

Exemplul 1:

inno.in

5 4
7 7 6 1 62

inno.out

1

Explicație

Singura posibilitate este eliminarea secvenței 7 7 6 1. Rămâne doar numărul 62, care are 5 biți de 1.