Vizualizare sursă pentru „3758 - inno”

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

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

După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația <code>&</code> pe biți asupra lor rezultatul este un număr care are cel puțin <code>k</code> biți de <code>1</code> în baza <code>2</code>. De exemplu, dacă <code>a=(1,2,3,4,5,7)</code> și <code>k=2</code>, atunci prin eliminarea secvenței <code>1,2,3,4</code> rămân elementele <code>5,7</code>, iar <code>5 & 7 = 5</code>, care are <code>2</code> biți de <code>1</code> în baza <code>2</code>. Dar dacă se elimină secvența <code>3,4,5</code> atunci rămân elementele <code>1,2,7</code>, iar <code>1 & 2 & 7 = 0</code>, 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 <code>input.txt</code> conține pe prima linie numerele naturale <code>n</code> și <code>k</code>. Pe linia a doua se află <code>n</code> numere naturale reprezentând elementele șirului.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> 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 =

* <code>3 ≤ n ≤ 200.000</code>;
* <code>1 ≤ k ≤ 29</code>;

== Exemplul 1 ==
input.txt:

4 2

10 7 5 15

output.txt:

5

Explicație:

Modalitățile sunt:

- se elimină <code>10</code> și rămâne șirul <code>7 5 15</code>, iar <code>7 & 5 & 15 = 5</code>, care are <code>2</code> biți de <code>1</code>

- se elimină <code>10 7</code> și rămâne șirul <code>5 15</code>, iar <code>5 & 15 = 5</code>, care are <code>2</code> biți de <code>1</code>

- se elimină <code>10 7 5</code> și rămâne șirul <code>15</code>, iar <code>15</code> are <code>4</code> biți de <code>1</code>

- se elimină <code>7 5</code> și rămâne șirul <code>10 15</code>, iar <code>10 & 15 = 10</code> are <code>2</code> biți de <code>1</code>

- se elimină <code>7 5 15</code> și rămâne șirul <code>10</code>, iar <code>10</code> are <code>2</code> biți de <code>1</code>

== Exemplul 2 ==
input.txt:

5 4

7 7 6 1 62

output.txt:

1

Explicație:

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

== Exemplul 3 ==
input.txt:

999999999999 4

7 7 6 1 62

Output:

Invalid input constraints.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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))

</syntaxhighlight>