# PBinfo #4815 – anagrame6 – Rezolvare C++ Sursa: Codul lui Andrei Limbaj: C++ Autor rezolvare: Darius ## Enunț 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. De exemplu, dacă șirul A este șirul abdacgacd și considerăm A[3, 8] = dacgac, atunci range(a) = 5 - 2 = 3 (pentru că, în A[3, 8], litera a apare pe pozițiile 2 și 5), range(c) = 6 - 3 = 3 și range(l) = 0 pentru toate celelalte litere l ∈ {b, d, e, f, g, ..., z}. Șirul suport asociat lui A[3, 8] este astfel aaaccc. Un șir de caractere S[1] este o anagramă a șirului S[2] dacă S[1] este identic cu S[2] sau dacă S[1] se poate obține din S[2] prin schimbarea ordinii caracterelor. De exemplu, șirul de caractere tamara este o anagramă a șirului armata. Două anagrame se consideră a fi distincte dacă ele diferă în cel puțin o poziție. De exemplu, șirul de caractere aab are trei anagrame distincte: aab, aba, baa. 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]. Cerințe Problema are două cerințe, cerința de rezolvat fiind dată de C ∈ {1, 2}. Pentru ambele cerințe, se dau șirul A și M operații care se vor efectua în ordine. 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. Date de intrare Pe prima linie a fișierului de intrare anagrame.in se află numerele naturale C, N și M, unde C este numărul cerinței (1 sau 2), iar N și M au semnificația din enunț. Pe a doua linie se află șirul A, cele N caractere ale sale nefiind separate prin spații. Pe fiecare dintre următoarele M linii se află datele care descriu câte o operație: O operație de actualizare este descrisă prin caracterul c și un număr natural poz, cu semnificația din enunț. O operație de generare este descrisă prin perechea x, y de numere naturale, cu semnificația din enunț. Valorile aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu. Date de ieșire Fișierul de ieșire anagrame.out va conține: Dacă C = 1: pe prima linie, șirul suport minim lexicografic cerut la cerința 1. Dacă C = 2: pentru fiecare generare câte o linie, ce conține numărul cerut în cerința 2, în ordinea corespunzătoare generărilor date. Restricții și precizări 1 ≤ N, M ≤ 100.000 1 ≤ x ≤ y ≤ N Se garantează că, pentru oricare operație de generare din testele de evaluare, șirul suport va conține cel puțin un caracter. În cadrul unei actualizări este permisă înlocuirea literei de pe poziția poz cu ea însăși. Șirul de caractere S[1], ..., S[k] este lexicografic mai mic decât șirul T[1], ..., T[l] dacă (i) k < l și S[i] = T[i] pentru oricare 1 ≤ i ≤ k, sau (ii) există un 1 ≤ i ≤ min(k, l) astfel încât S[1] = T[1], …, S[i-1] = T[i-1] și S[i] < T[i]. Pentru 8 puncte, C = 1; N ≤ 10.000; nu există actualizări, iar șirul A are toate literele identice Pentru 16 puncte, C = 1; 1 ≤ N, M ≤ 500 Pentru 24 puncte, C = 1; N ≤ 10.000; nu există actualizări Pentru 12 puncte, C = 1 Pentru 8 puncte, C = 2; N ≤ 10.000; nu există actualizări, iar șirul A are toate literele identice} Pentru 12 puncte, C = 2; y-x ≤ 5; 1 ≤ M ≤ 50 și 1 ≤ N ≤ 10.000 Pentru 8 puncte, C = 2; N ≤ 10.000; înainte de toate actualizările și după fiecare actualizare, șirul A nu va conține alte litere în afară de a și b Pentru 12 puncte, C = 2 Exemplul 1: anagrame.in 1 5 5 abcar b 3 1 4 r 4 r 2 2 4 anagrame.out aaab Explicație După prima actualizare, șirul A devine abbar. A doua operație este o generare. Șirul suport obținut pentru abba este aaab. După următoarele două actualizări, șirul A devine arbrr, iar șirul suport pentru rbr corespunzător celei de a doua generări este rr. Șirul suport minim lexicografic dintre cele două obținute este aaab. Exemplul 2: anagrame.in 2 5 5 abcar b 3 1 4 r 4 r 2 2 4 anagrame.out 4 1 Explicație Pentru prima generare (1, 4) șirul suport obținut este aaab, care are patru anagrame distincte: aaab, aaba, abaa, baaa. După următoarele două operații, șirul suport pentru rbr este rr, care are o singură anagramă. ## Cod sursă C++ ```cpp #include #define MOD 1999999973 ///O(sigma * M * logN) using namespace std; const int Nmax = 100005; int N, M, C, Ans; int SirMin[30]; char A[Nmax]; unsigned long long Fact[30 * Nmax]; set S[30]; ifstream f("anagrame.in"); ofstream g("anagrame.out"); void precl() ///precalculam factorialele numerelor mai mici ca Nmax { Fact[0] = 1; for (int i = 1; i < 26 * Nmax; i++) Fact[i] = (1LL * i * Fact[i-1])%MOD; } int elg(int a, int b) ///exponentierea logaritmica { int rez=1; while (b>1) { if (b%2==1) rez=(1LL * rez * a)%MOD; a=(1LL * a * a)%MOD; b=b/2; } return (1LL * a * rez)%MOD; } void actualizez_min(int A[], int B[]) { int lg_A = 0, lg_B = 0; for (int i = 0; i <= 25; i++) { lg_A += A[i]; lg_B += B[i]; } bool ok = false; for (int i = 0; i <=25 && !ok; i++) { lg_A -= A[i]; lg_B -= B[i]; if (A[i] > B[i]) { if (lg_B > 0) ok = true; else break; } if (A[i] < B[i]) { if (lg_A > 0) break; else ok = true; } } if (ok) for (int i = 0; i <=25; i++) B[i] = A[i]; } void Generare(int x, int y, int &Rez) { int Range[30], P=1, Nr = 0; for (int i = 0; i<= 25; i++) { Range[i] = 0; auto it1 = S[i].lower_bound(x); if (it1 == S[i].end()) continue; auto it2 = S[i].upper_bound(y); if (it2 ==S[i].begin()) continue; it2--; Range[i] = *it2 - *it1; if (Range[i] < 0) Range[i] = 0; P = (1LL * P * Fact[Range[i]])% MOD; Nr += Range[i]; } Rez = (1LL * Fact[Nr] * elg(P, MOD - 2))%MOD; if (C==1) actualizez_min(Range, SirMin); } void load () { f >> C >> N >> M; assert (C==1 || C==2); assert (N <=100000); assert (M <= 100000); for (int i = 1; i <= N; i++) /// initializam seturile care mentin pentru fiecare litera pozitiile din sir { f >> A[i]; assert (islower(A[i])); S[A[i] - 'a'].insert(i); } for (int i = 0; i <=25; i++) SirMin[i] = 0; SirMin[25] = N * 30; A[N+1]='\n'; for (int i = 1; i <=M; i++) { int x = 0, y, poz; char s[Nmax]; f >> s; if (isdigit(s[0])) ///operatie generare { for (int j=0; s[j]; j++) x = x*10 + (int)s[j] - '0'; f>>y; assert (x<=y); assert (y<=N); Generare(x, y, Ans); if (C==2) g << Ans << '\n'; } else /// operatie update { assert(islower(s[0])); f >> poz; S[A[poz]-'a'].erase(poz); S[s[0]-'a'].insert(poz); A[poz] = s[0]; } } if (C==1) { for (int i = 0; i <= 25; i++) for (int j = 1; j<= SirMin[i]; j++) g<<(char)(i + 'a'); g << '\n'; } } int main() { precl(); load(); return 0; } ``` ## Resurse - [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4815) - [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4815/cod.cpp) - [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4815/main.cpp) - [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)