== include(page="template/taskheader" task_id="inno") ==
Se dau numerele naturale *N* și [*K*], precum și un șir [$[*a[~1~], a[~2~], . . . , a[~N~]*]$] de numere naturale nenule. Din șir se 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.
Se dau numerele naturale *N* și [*K*], precum și un șir [$[*a[~1~], a[~2~], . . . , a[~N~]*]$] de numere naturale nenule. Din șir se 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.
h2. Cerință
Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.
h2. Date de intrare
Fișierul de intrare $inno.in$ ...
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, separate prin câte un spațiu.
h2. Date de ieșire
În fișierul de ieșire $inno.out$ ...
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.
h2. Restricții
h2. Restricții și precizări
* $... ≤ ... ≤ ...$
* $3 ≤ *N* ≤ 200 000$
* $1 ≤ *K* ≤ 29$
* $0 ≤ [*a[~i~]*] ≤ 2[^31^] − 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)~]$
* Pentru teste în valoare de *12* puncte: $1 ≤ *K* ≤ 2 și 3 ≤ *N* ≤ 25$
* Pentru alte teste în valoare de *23* de puncte: $500 ≤ *N* ≤ 8 000$
* Pentru alte teste în valoare de *65* de puncte: Nu există restricții suplimentare.
h2. Exemplu
table(example).
|_. inno.in |_. inno.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
table(example).
|_. inno.in |_. inno.out |_. Explicații |
| 4 2
10 7 5 15
| 5
| 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
|
| 5 4
7 7 6 1 62
| 1
| Singura posibilitate este eliminarea secvenței [$7 7 6 1$].
Rămâne doar numărul [$62$], care are 5 biți de 1.
|
== include(page="template/taskfooter" task_id="inno") ==
