3758 - inno

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 input.txt 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 output.txt 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;

Exemplul 1

input.txt:

4 2

10 7 5 15

output.txt:

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 2

input.txt:

5 4

7 7 6 1 62

output.txt:

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.

Exemplul 3

input.txt:

999999999999 4

7 7 6 1 62

Output:

Invalid input constraints.

Rezolvare

def verify_constraints(n, k):
    if not (3 <= n <= 200000 and 1 <= k <= 29):
        print("Invalid input constraints.")
        exit()

def count_bit(v):
    v = v - ((v >> 1) & 0x55555555)
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333)
    c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
    return c

def bsearch(p, u, key, k):
    m = 0
    while p < u:
        m = (p + u) // 2
        if dr[m] & key < k:
            p = m + 1
        else:
            u = m

    m = (p + u) // 2
    if dr[m] & key < k:
        m += 1
    return m

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:
    n, k = map(int, fin.readline().split())
    verify_constraints(n,k)
    a = [0] + list(map(int, fin.readline().split()))
    st = [0] * (n + 1)
    dr = [0] * (n + 1)
    x = -1
    y = 0
    val = 0
    sol = 0

    st[1] = a[1]
    dr[n] = a[n]

    for i in range(2, n + 1):
        st[i] = st[i - 1] & a[i]

    for i in range(n - 1, 0, -1):
        dr[i] = dr[i + 1] & a[i]

    if count_bit(st[1]) < k:
        x = 0

    if count_bit(dr[n]) < k:
        y = n + 1

    if x < 0:
        x = 1
        i = 2
        while i <= n:
            if count_bit(st[i]) >= k:
                x = i
            i += 1

    if not y:
        y = n
        i = n - 1
        while i >= 1:
            if count_bit(dr[i]) >= k:
                y = i
            i -= 1

    if x == n:
        fout.write(str(n * (n + 1) // 2))
    elif x == 0 and y == n + 1:
        fout.write("0")
    elif 1 <= x < n and y == n + 1:
        fout.write(str(x))
    elif x == 0 and 1 < y <= n:
        fout.write(str(n - y + 1))
    elif x == 0 and y == 0:
        fout.write("1")
    else:
        sol = n - y + 1
        for i in range(1, x + 1):
            val = bsearch(y, n, st[i], k)
            sol += (n - val + 2)

        fout.write(str(sol))