Vezi solutiile trimise | Statistici

Invalid task identifier

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ă.

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?