Involuciones
Durante la Olimpiada de Informática de Centroamérica y el Caribe (OICC), los organizadores están preparando un desafío matemático basado en permutaciones.
Una permutación de longitud
se denomina involución si cumple que
para todo
.
Se define una inversión de una permutación como un par de índices tal que
y
.
Dado un entero positivo , tu tarea es determinar, para cada entero
en el intervalo
, cuántas involuciones de longitud
tienen exactamente
inversiones, módulo
.
Entrada
La primera línea contiene dos enteros y
(
) la longitud de las permutaciones y el máximo número de inversiones que se debe considerar.
Salida
Imprime una cadena binaria de longitud .
El carácter en la posición (comenzando desde
) debe ser:
0si la cantidad de involuciones de longitudcon exactamente
inversiones es par.
1si dicha cantidad es impar.
Los caracteres deben aparecer en orden creciente de , desde
hasta
.
Subtareas
Esta tarea está compuesta por subtareas.
Los puntos de una subtarea se otorgan solo si se aceptan todos los casos de esa subtarea.
| Subtarea | Puntos | Restricciones adicionales | Dependencias |
|---|---|---|---|
| Sin restricciones adicionales |
Ejemplos
Entrada 1
3 9
Salida 1
1001000000
Comments