Caja de puros


Submit solution


Points: 100 (partial)
Time limit: 4.0s
Java 8 6.0s
Python 12.0s
Memory limit: 1G

Author:
Problem types
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Prolog, Python, Swift, VB

Aplicamos la siguiente operación m veces en la secuencia (1,2,..., n), y resultó en (a_1,..., a_n).

  • Borra un elemento. Luego, agregue el elemento borrado al principio o al final de la secuencia.

Encuentra el número de sucesiones posibles de m operaciones válidas, módulo 998244353.

Dos secuencias de operaciones se consideran iguales cuando, en cada operación, se elige el mismo elemento y se agrega a la misma posición.

Restricciones
  • 2 \leq n, m \leq 3000.

a_1,..., a_n es una permutación de 1,..., n.

Entrada

La entrada se da en el siguiente formato

n m
a1, ..., an
Salida

Imprime el número de posibles secuencias de m operaciones, que al aplicarse a (1,2,..., n) da como resultado (a_1,..., a_n) módulo 998244353.

Ejemplo de entrada 1
5 2
1 2 4 5 3
Ejemplo de salida 1
5

Hay cinco posibles secuencias de operaciones, como sigue:

  • Borre 1 y agréguele al principio, lo que da como resultado (1,2,3,4,5). Luego, borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3).

  • Borre 3 y agréguelo al principio, lo que da como resultado (3,1,2,4,5). Luego, borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3).

  • Borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3). Luego, borre 1 y agréguelo al principio, lo que da como resultado (1,2,4,5,3).

  • Borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3). Luego, borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3) .

  • Borre 5 y agréguelo al final, lo que da como resultado (1,2,3,4,5). Luego, borre 3 y agréguelo al final, lo que da como resultado (1,2,4,5,3).

Ejemplo de entrada 2
2 16
1 2
Ejemplo de salida 2
150994942

Dos de los cuatro tipos de operaciones no tienen ningún efecto sobre la secuencia y los otros dos intercambian los dos elementos. A partir de este hecho, podemos demostrar que hay \frac{4^m}{2} = 2^{31} = 2147483648 secuencias de operaciones, la mitad de todas las secuencias posibles, que queremos contar. Por lo tanto, la respuesta es 2147483648 módulo 998244353, es decir, 150994942.

Ejemplo de entrada 3
10 3000
3 7 10 1 9 5 4 8 6 2
Ejemplo de salida 3
129989699

Comments

There are no comments at the moment.