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

<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>