Cadena Skibidi#13091
Para una cadena , sea la cantidad de subcadenas distintas y no vacías de . Por ejemplo, f(\mathtt{aab}) = 5: las subcadenas son , , , , .
Se te dan un entero y una cadena binaria de longitud n-2, indexada como t_1, \ldots, t_{n-2}.
Decimos que una cadena de longitud es Skibidi si al deslizar una ventana de longitud a lo largo de se obtienen n-2 ventanas y, para cada 1 \le i \le n-2, la -ésima ventana cumple t_i:
Determina la cadena Skibidi lexicográficamente menor formada por letras latinas minúsculas.
^\daggerOperación módulo. Para enteros positivos y , u \bmod v denota el resto de dividir entre .
Por ejemplo, para s = \mathtt{aabcba} tenemos importante ! : debe resolverse con una dp de O(3^6*n)
por lo que t = \mathtt{1010}, es decir, t_1=1,\ t_2=0,\ t_3=1,\ t_4=0.
La primera línea contiene un único entero (1 \le T \le 10^4) — la cantidad de casos de prueba.
La primera línea de cada caso de prueba contiene un entero (3 \le n \le 2 \cdot 10^5) — la longitud de la cadena buscada.
La segunda línea de cada caso de prueba contiene una cadena binaria de longitud n-2 (t_i \in \{\mathtt{0}, \mathtt{1}\}).
Se garantiza que la suma de sobre todos los casos de prueba no excede 2 \cdot 10^5.
Para cada caso de prueba, imprime la cadena lexicográficamente menor formada por letras latinas minúsculas que cumpla las condiciones.
Ejemplo 1
Para el primer caso de prueba, s = \mathtt{aabcba}:
i = 1: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
i = 2: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
i = 3: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
i = 4: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
Por lo tanto, la resultante es , como se requiere.
Para el segundo caso de prueba, s = \mathtt{abcbaa}:
i = 1: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
i = 2: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
i = 3: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
i = 4: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
Por lo tanto, la resultante es , como se requiere.
Para el tercer caso de prueba, s = \mathtt{aaabcaa}:
i = 1: tiene f = 3 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
i = 2: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
i = 3: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
i = 4: tiene f = 6 subcadenas distintas no vacías, por lo que f \bmod 2 = 0.
i = 5: tiene f = 5 subcadenas distintas no vacías, por lo que f \bmod 2 = 1.
Por lo tanto, la resultante es , como se requiere.
Subtarea ( puntos): (t=\mathtt{00000 \ldots 0})
Subtarea ( puntos): (t=\mathtt{11111\ldots 1})
Subtarea ( puntos): (1 \le \sum n \le 1000)
Subtarea ( puntos): (1 \le \sum n \le 10^4)
Subtarea ( puntos): Sin restricciones adicionales