# PBinfo #3758 – inno – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define inFile "inno.in"
#define outFile "inno.out"
#define nmax 200003
using namespace std;
int a[nmax], st[nmax], dr[nmax], n, k;
long long nrSecv;
int NrBiti_1(int n)
{
    int s = 0;
    while (n > 0)
    {
        n = (n & (n - 1));
        s++;
    }
    return s;
}
void Citire()
{
    ifstream fin(inFile);
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
}
void Rezolvare()
{
    int i, j, x, y, stop;
    ofstream fout(outFile);
    x = 0;
    st[0] = (1 << 30) - 1;
    stop = 0;
    for (i = 1; i <= n && !stop; i++)
    {
        st[i] = st[i - 1] & a[i];
        if (NrBiti_1(st[i]) >= k) x = i;
        else stop = 1;
    }
    if (x == n)
    {
        nrSecv = 1LL * n * (n + 1) / 2 - 1;
        fout << nrSecv << "\n";
        fout.close();
        return;
    }
    y = n + 1;
    dr[n + 1] = (1 << 30) - 1;
    stop = 0;
    for (i = n; i >= 1; i--)
    {
        dr[i] = dr[i + 1] & a[i];
        if (NrBiti_1(dr[i]) >= k) y = i;
        else stop = 1;
    }
    if (x == 0 && y == n + 1) /// nu sunt solutii
    {
        fout << "0\n";
        fout.close();
        return;
    }
    if (y == n + 1)
    {
        fout << x << "\n";
        fout.close();
        return;
    }
    if (x == 0)
    {
        fout << (n - y + 1) << "\n";
        fout.close();
        return;
    }
    j = y;
    nrSecv = (n - y + 1);
    for (i = 1; i <= x && j <= n; i++)
    {
        while (j <= n && NrBiti_1(st[i] & dr[j]) < k)
            j++;
        nrSecv += (n - j + 2);
    }
    fout << nrSecv << "\n";
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3758)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3758/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3758/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)