Fişierul intrare/ieşire:	miculstring.in, miculstring.out	Sursă	Lot Bistrița Seniori 2026, Baraj 3
Autor	Vlad-Mihai Bogdan	Adăugată de	Bogdan Vlad-Mihai •bogdanvladmihai
Timp execuţie pe test	2 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Micul String

Se numeşte subsecvenţă a unui şir de caractere s un şir de caractere t cu proprietatea că există doi indici i şi j cu 0 ≤ i ≤ j < |s| astfel încât t = s_is_i+1s_i+2…s_j.

Pentru un tuplu de şiruri de caractere (s₀, s₁, s₂, …, s_K-1) vom defini f(s₀, s₁, s₂, …, s_K-1) ca fiind şirul minim lexicografic ce se poate obţine prin următorul procedeu:

• Pentru fiecare şir s_i, se alege o subsecvenţă nevidă t_i a sa;
• Se concatenează t₀, t₁, t₂, …, t_K-1, şirul obţinut fiind rezultatul procedeului.

Un şir de caractere a₀a₁…a_n-1 este mai mic lexicografic decât un alt şir de caractere b₀b₁…b_m-1 dacă şi numai dacă:

• Există un indice i 0 ≤ i < min(n, m) pentru care a₀a₁…a_i-1 = b₀b₁…b_i-1 şi a_i < b_i; sau
• n < m şi a₀a₁…a_n-1 = b₀b₁…b_n-1.

Cerinţă

Se dau un număr natural N, un şir de caractere de lungime N, notat w, un număr natural K şi un şir de K numere naturale nenule l₀, l₁, l₂, …, l_K-1. Să se numere câte tupluri de K şiruri de caractere, (s₀, s₁, s₂, …, s_K-1), respectă următoarele condiţii:

• Toate şirurile conţin doar litere mici ale alfabetului englez;
• |s_i| = l_i, ∀ 1 ≤ i ≤ K;
• f(s₀, s₁, s₂, …, s_K-1) = w.

Deoarece acest număr poate fi mare, se cere restul acestuia la împărţirea prin 998 244 353.

Detalii de implementare

Concurenţii vor avea de implementat o singură funcţie:

int solve(int N, int K, std::string w, std::vector<int> l);

care primeşte ca parametri:

• N, numărul de caractere din şirul w;
• K, numărul de şiruri dintr-un tuplu;
• Şirul w (indexat de la 0);
• l, reprezentând lungimile şirurilor (indexat de la 0).

Funcţia solve va fi apelată o singură dată per proces.

{**Din cauza limitărilor impuse de infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de aici}

Restricţii

• 1 ≤ K ≤ N ≤ 200
• 1 ≤ l_i ≤ 200, 0 ≤ i ≤ N - 1
• Şirul w este format doar din litere mici ale alfabetului englez.
• Vom considera w_i al i-lea caracter din şirul w.

Exemple

Explicaţii

Pentru primul exemplu, singurul tuplu valid este ("b", "ab", "z").

Cum se trimit solutii?