1737 - K Siruri

Se consideră un număr natural K și o secvență de N șiruri s[1], s[2], …, s[N]. Fiecare șir este format din cifre distincte. Pentru două șiruri s[i] și s[j] se definește operația de scădere (–) astfel: s[i]-s[j] va conține doar șirul de cifre care apar în s[i], dar nu apar în s[j]. De exemplu, dacă s[i]=(1,3,8) și s[j]=(2,9,3), atunci s[i]-s[j]=(1,8). Această operație nu este asociativă, (s[i]-s[j])-s[p] este diferită de s[i]-(s[j]-s[p]). De aceea, dacă se alege un subșir s[i1], s[i2], …, s[ip] din secvență, atunci convenim ca s[i1]-s[i2]-...-s[ip] să se execute de la dreapta la stânga.

Exemplu: (1,2,3)-(2,3)-(1,3)=(1,2,3)-(2)=(1,3). S-au obținut două cifre distincte.

Cerința

Să se determine numărul subșirurilor nevide s[i1], s[i2], …, s[ip] din secvența s[1], s[2], …, s[N] asupra cărora, dacă se efectuează operația de scădere (adică s[i1]-s[i2]-...-s[ip]), se obțin cel puțin K cifre distincte. Pentru că numărul subșirurilor poate fi foarte mare, atunci el se va calcula modulo 123457.

Date de intrare

Fișierul de intrare ksiruriIN.txt conține pe prima linie numerele naturale K și N. Pe următoarele N linii se află câte un șir s[i]. Linia i+1, i = 1..N, va conține valorile m c[1] c[2] .. c[m], unde m este numărul de termeni al șirului s[i], iar c[1], c[2], …, c[m] sunt cifrele distincte ale șirului s[i]. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Date de ieșire

Fișierul de ieșire ksiruriOUT.txt va conține reprezentând numărul de subșiruri, modulo 123457.

Restricții și precizări

• 1 ≤ K ≤ 8
• 2 ≤ N ≤ 50 000
• 1 ≤ i1 < i2 < ... < ip ≤ N

Exemplu 1:

ksiruriIN.txt

3 3
5 5 6 7 8 9
3 4 5 6
3 7 8 9 

ksiruriOUT.txt

6

Explicație

s1 = 5 6 7 8 9

s2 = 4 5 6

s3 = 7 8 9

Cele șase subșiruri nevide sunt:

s1, s1-s2, s1-s2-s3, s2, s2-s3, s3

Exemplu 2:

ksiruriIN.txt

9 3
5 5 6 7 8 9
3 4 5 6
3 7 8 9 

ksiruriOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line="1"> import sys from functools import reduce

nmax = 50005 MOD = 123457 inFile = "ksiruriIN.txt" outFile = "ksiruriOUt.txt"

a = [0] * nmax d = [0] * 1030 v = [0] * 1030

def verifica_restrictii(K, n):

   if not (1 <= K <= 8 and 2 <= n <= 50000):
       return False
   return True

def citire():

   global a, K, n
   try:
       with open(inFile, 'r') as fin:
           K, n = map(int, fin.readline().strip().split())
           if not verifica_restrictii(K, n):
               return False
           for i in range(1, n + 1):
               linie = list(map(int, fin.readline().strip().split()))
               m = linie[0]
               for x in linie[1:m+1]:
                   a[i] |= (1 << x)
       return True
   except Exception as e:
       print(f"Eroare la citire: {e}")
       return False

def nr_biti(n):

   cnt = 0
   while n > 0:
       cnt += 1
       n &= (n - 1)
   return cnt

def dinamica():

   global a, d, v, n, MOD
   d[a[n]] = 1
   for i in range(n - 1, 0, -1):
       for j in range(1024):
           v[j] = d[j]
       x = a[i]
       v[x] += 1
       if v[x] == MOD:
           v[x] = 0
       for j in range(1024):
           if d[j] > 0:
               y = x ^ (x & j)
               v[y] += d[j]
       for j in range(1024):
           d[j] = v[j] % MOD

def afisare():

   cnt = 0
   for i in range(1024):
       if nr_biti(i) >= K and d[i] > 0:
           cnt += d[i]
   cnt %= MOD
   with open(outFile, 'w') as fout:
       fout.write(f"{cnt}\n")

def main():

   if not citire():
       with open(outFile, 'w') as fout:
           fout.write("Datele nu corespund restrictiilor impuse\n")
       return
   dinamica()
   afisare()

if __name__ == "__main__":

   main()

</syntaxhighlight>