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 ksiruri.in 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].

Date de ieșire

Fișierul de ieșire ksiruri.out 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

ksiruri.in

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

ksiruri.out

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema KSiruri:

#include <bits/stdc++.h>
#define nmax 50005
#define MOD 123457
#define inFile "ksiruri.in"
#define outFile "ksiruri.out"

using namespace std;

int a[nmax], n, K;
int d[1030], v[1030];

void Citire()
{
    int i, j, x, m;
    ifstream fin(inFile);
    fin >> K >> n;
    for (i = 1; i <= n; ++i)
    {
        fin >> m;
        for (j = 1; j <= m; ++j)
        {
            fin >> x;
            a[i] |= (1 << x);
        }
    }
    fin.close();
}

inline int NrBiti(int n)
{
    int cnt = 0;
    while (n > 0)
    {
        cnt++;
        n = n & (n - 1);
    }
    return cnt;
}

void Dinamica()
{
    int i, j, x, y;
    d[a[n]] = 1;
    for (i = n - 1; i >= 1; --i)
    {
        for (j = 0; j < 1024; ++j)
            v[j] = d[j];
        x = a[i];
        v[x]++;
        if (v[x] == MOD) v[x] = 0;
        for (j = 0; j < 1024; ++j)
            if (d[j] > 0)
            {
                y = x ^ (x & j);
                v[y] += d[j];
            }
        for (j = 0; j < 1024; ++j)
            d[j] = v[j] % MOD;
    }
}

void Afisare()
{
    int i, cnt;
    cnt = 0;
    for (i = 0; i < 1024; ++i)
        if (NrBiti(i) >= K && d[i] > 0)
            cnt += d[i];
    cnt %= MOD;
    ofstream fout(outFile);
    fout << cnt << "
";
    fout.close();
}

int main()
{
    Citire();
    Dinamica();
    Afisare();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1737 KSiruri

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1737 KSiruri de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1737 KSiruri