Lista de probleme 3

Considerăm numerele naturale N, X, Y, M[1], M[2], ..., M[N]. Șirul de numere naturale A[1], A[2], ..., A[N] este numit bun dacă următoarele condiții sunt satisfăcute simultan:

• A[1] OR A[2] OR ... OR A[N] = X, unde OR reprezintă operația sau pe biți.
• A[1] XOR A[2] XOR ... XOR A[N] = Y, unde XOR reprezintă operația sau exclusiv pe biți.
• A[i] AND M[i] = M[i], pentru 1 ≤ i ≤ N, unde AND reprezintă operația și pe biți.

Se dau N, X, Y și M[1], M[2], ..., M[N], cu semnificația din enunț. Să se determine dacă există șiruri bune, respectiv să se determine numărul de șiruri bune, modulo 1.000.000.007.

Se consideră șirul de litere mici ale alfabetului englez A[1], ..., A[N].

Fie succesiunea de caractere alăturate din șir A[x], A[x + 1], ..., A[y], unde 1 ≤ x ≤ y ≤ N, pe care o notăm cu A[x, y]. Pentru oricare literă mică a alfabetului englez l, definim range(l) ca fiind 0, dacă l apare cel mult o dată în A[x, y]. Altfel, valoarea range(l) este egală cu diferența dintre cea mai mare și cea mai mică poziție pe care litera l apare în A[x, y].
Șirul suport asociat lui A[x, y] este șirul de caractere minim lexicografic ce conține fiecare literă l de range(l) ori. Asupra șirului se efectuează două tipuri de operații:

• Actualizare: dându-se litera c și poziția poz, se înlocuiește A[poz] cu c.
• Generare: dându-se perechea x, y, se generează șirul suport al lui A[x, y].

• Dacă C = 1: determinați șirul suport minim lexicografic dintre cele obținute în urma tuturor operațiilor de generare.
• Dacă C = 2: pentru fiecare operație de generare dată, determinați numărul de anagrame distincte ale șirului suport obținut, modulo 1999999973.

Privit din satelit, Golful Biscayne (Florida) este format din n × m celule pătratice, fiecare celulă fiind umplută fie cu pământ, fie cu apă. Celulele umplute cu pământ sunt grupate în insule: două celule umplute cu pământ fac parte din aceeași insulă dacă și numai dacă se poate ajunge de la una la cealaltă prin deplasare (în sus, jos, stânga sau dreapta) doar pe pământ.

Golful poate fi văzut, astfel, ca o matrice A cu n linii și m coloane (numerotate de la 1), unde A[i][j] = 1 dacă celula de pe linia i și coloana j este umplută cu pământ și A[i][j] = 0 dacă este umplută cu apă.

Spunem că o insulă se află la stânga unei coloane c dacă și numai dacă toate celulele ce intră în alcătuirea insulei sunt strict la stânga coloanei c, adică sunt situate pe coloane strict mai mici decât c. Analog, stabilim dacă o insulă se află la dreapta unei coloane c, respectiv deasupra sau dedesubtul unei linii l. De exemplu, în desenul de mai sus, insulele A, B și C sunt la stânga coloanei 7, insula E este la dreapta coloanei 7, iar insula D nu este nici la stânga, nici la dreapta coloanei 7. De asemenea, insulele A și B sunt deasupra liniei 3, iar insulele C, D și E sunt dedesubtul liniei 4. Mai mult, insulele C, D și E nu sunt nici deasupra, nici dedesubtul liniei 5.

Problema are trei cerințe, cerința de rezolvat fiind dată de T ∈ {1, 2, 3}.

• T = 1. Determinați numărul de celule din golf ce sunt umplute cu pământ.
• T = 2. Determinați numărul de insule din golf ce conțin un număr maxim de celule. Dacă nu există nicio insulă, atunci valoarea acestui număr este 0.
• T = 3. Se dau, în ordine, Q interogări, fiecare fiind descrisă printr-o literă și un număr natural
  nenul p. Determinați valoarea produsului a × b, știind că:
  • Dacă litera este C, atunci a reprezintă numărul de celule din toate insulele ce se află la stânga coloanei p (1 ≤ p ≤ m) și b numărul de celule din toate insulele ce se află la dreapta coloanei p.
  • Dacă litera este L, atunci a reprezintă numărul de celule din toate insulele ce se află deasupra liniei p (1 ≤ p ≤ n) și b numărul de celule din toate insulele ce se află dedesubtul liniei p.