Digamos que una operación es esencial cuando es la última operación que se aplica a ese número.

La condición de que el número de operaciones esenciales debe satisfacer:

Considere el caso que hicimos ~L~ operaciones esenciales que mueven un número al principio y ~R~ operaciones esenciales que mueven un número al final. Entonces, ~a_{L + 1},..., a_{n - R}~ nunca fueron objeto de una operación, por lo que su orden relativo no cambió desde el estado inicial ~(1,2,..., n)~.

Por tanto, esta secuencia debe aumentar de forma monótona.

Solución en ~O(n^2\cdot m)~

El número elegido en la i-ésima última operación esencial que mueve un número al principio será el i-ésimo término en la secuencia final, por lo que esta operación debe elegir a ~a_i~. De manera similar, la i-ésima última operación esencial que mueve un número al final debe elegir a ~a_{n - i + 1}~. Una operación no esencial puede elegir cualquier número que será elegido por una operación posterior y moverlo al principio o al final.

De estos, para ~L + R \le n~ tal que ~a_{L + 1},..., a_{n - R}~ aumenta monótonamente, habrá una secuencia única de operaciones si se decide lo siguiente:

1. las primeras ~L~ operaciones esenciales mueven un número al principio;

2. las últimas ~R~ operaciones esenciales mueven un número hasta el final;

3. para cada operación no esencial:

   • si mueve un número al principio o al final;
   • qué operación esencial moverá el número movido por esa operación.

Así, podemos encontrar el número de sucesiones de operaciones de longitud ~i~ que contiene ~l~ operaciones esenciales al principio y ~r~ operaciones esenciales hasta el final, ~dp [i] [l] [r]~, con la siguiente programación dinámica: (la fórmula de recurrencia corresponde a construir la secuencia de operaciones hacia atrás).

    for i = 0..m, l = 0..n, r = 0..n
        dp [i + 1] [l] [r] + = dp [i] [l] [r] * 2 * (l + r)
        dp [i + 1] [l + 1] [r] + = dp [i] [l] [r]
        dp [i + 1] [l] [r + 1] + = dp [i] [l] [r]

Después de calcular ~dp [i] [l] [r]~, podemos sumar ~dp [m] [L] [R]~ sobre todo ~L + R \le n~ tal que ~a_{L + 1},..., a_{n - R}~ aumenta monótonamente para encontrar la respuesta, pero este método tendrá la complejidad de ~O(n^2\cdot m)~.

Otra solución en ~O(n^2\cdot m)~

Aquí, sea ~j = l + r~ (es decir, el número de enteros que estarán sujetos a alguna operación).

Sea ~dp2 [i] [l] [r]~ el número de formas de decidir lo siguiente para una secuencia de operaciones de longitud ~i~ que contiene ~j~ operaciones esenciales:

• si cada operación es esencial;
• para cada operación no esencial, qué operación esencial moverá el número movido por esa operación.

Elegir cuáles de las j operaciones esenciales moverán un número al principio determinará la secuencia de operaciones, así que tenemos ~dp [m] [l] [r] == dp2 [m] [l + r] * binom (l + r, l)~ (binom es el coeficiente binomial).

Podemos calcular ~dp2 [i] [j]~ de la siguiente manera:

    for i = 0..m, j = 0..n
        dp2 [i + 1] [j] + = dp2 [i] [j] * 2 * j
        dp2 [i + 1] [j + 1] + = dp2 [i] [j]

Ahora podemos resolver el problema en ~O (n\cdot m)~. tiempo, que es lo suficientemente rápido bajo las limitaciones.

Hay otra solución con combinatoria en lugar de dp.