Caja de puros.

View as PDF

Submit solution


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

Author:
Problem types
Allowed languages
C, C++, Java, Python

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.