Involuciones


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

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 p de longitud n se denomina involución si cumple que p_{p_i} = i para todo 1 \le i \le n.

Se define una inversión de una permutación como un par de índices (i, j) tal que i < j y p_i > p_j.

Dado un entero positivo k, tu tarea es determinar, para cada entero x en el intervalo [0, k], cuántas involuciones de longitud n tienen exactamente x inversiones, módulo 2.

Entrada

La primera línea contiene dos enteros n y k (1 \le k,n \le 10^6) la longitud de las permutaciones y el máximo número de inversiones que se debe considerar.

Salida

Imprime una cadena binaria de longitud k + 1.

El carácter en la posición x + 1 (comenzando desde 1) debe ser:

  • 0 si la cantidad de involuciones de longitud n con exactamente x inversiones es par.
  • 1 si dicha cantidad es impar.

Los caracteres deben aparecer en orden creciente de x, desde 0 hasta k.

Subtareas

Esta tarea está compuesta por 7 subtareas.

Los puntos de una subtarea se otorgan solo si se aceptan todos los casos de esa subtarea.

Subtarea Puntos Restricciones adicionales Dependencias
1 10 1 \le n \le 10, 1 \le k \le 50 -
2 10 1 \le n \le 20, 1 \le k \le 200 1
3 10 1 \le n \le 2000, 1 \le k \le 2 \cdot 10^5 1-2
4 10 1 \le n \le 2000, 1 \le k \le 5 \cdot 10^5 1-3
5 10 1 \le n \le 2000, 1 \le k \le 10^6 1-4
6 20 1 \le n \le 10^6, 1 \le k \le 5 \cdot 10^4 1-2
7 30 Sin restricciones adicionales 1-6

Ejemplos

Entrada 1
3 9
Salida 1
1001000000

Comments

There are no comments at the moment.