各操作について、その操作がその数に対する最後の操作である場合、本質的な操作 であると呼ぶことにします。

本質的な操作の回数についての必要条件

先頭に移動させる本質的な操作を \(L\) 回、末尾に移動させる本質的な操作を \(R\) 回行った場合を考えます。 このとき、\(a_{L+1},\dots,a_{n-R}\) は一度も操作の対象にならないため、これらの相対的な順序は初期状態 \((1,2,\dots,n)\) から 変わりません。よって、この数列は単調増加でなければなりません。

\(O(n^2m)\) 解法

先頭に移動させる本質的な操作のうち最後から \(i\) 番目で選んだ数は、最終的に先頭から \(i\) 番目の項になります。よって、\(a_i\) を選ばなければなりません。 同様に、末尾に移動させる本質的な操作のうち最後から \(i\) 番目のものでは、\(a_{n-i+1}\) を選ばなければなりません。 本質的でない操作では、（それ以降に操作の対象になる数であれば）何を選んでも、先頭と末尾のどちらに移動させても良いです。

以上のことから、\(a_{L+1},\dots,a_{n-R}\) が単調増加になるような \(L+R\le n\) に対して、次のことを決めると操作列が 一通りに定まります。

• どの \(L\) 個の操作が先頭に移動させる本質的な操作か
• どの \(R\) 個の操作が末尾に移動させる本質的な操作か
• 各本質的で無い操作について
  • 先頭に移動させるか、末尾に移動させるか
  • その操作と同じ数を操作する本質的な操作がどれか

よって、先頭に移動させる本質的な操作が \(l\) 回、末尾に移動させる本質的な操作が \(r\) 回が含まれる長さ \(i\) の操作列の数 dp[i][l][r] は 以下のような動的計画法で計算できます。（操作列を後ろから構築していくことをイメージして漸化式をたてています。）

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]

この dp[i][l][r] を計算したあと、\(a_{L+1},\dots,a_{n-R}\) が単調増加になるような \(L+R\le n\) それぞれについて、 \(dp[m][L][R]\) を足し上げれば答えが求まりますが、これでは計算量が \(O(n^2m)\) となってしまいます。

\(O(nm)\) 解法

ここで、\(j=l+r\) （つまり、 操作の対象になる整数の数）とおきます。

本質的な操作が \(j\) 回含まれる長さ \(i\) の操作列について、次のものの決め方を dp2[i][j] とします。

• 各操作が本質的であるかどうか
• 各本質的で無い操作について、その操作と同じ数を操作する本質的な操作がどれか

\(j\) 個のうちどれが先頭に移動させる本質的な操作かを決めれば操作列が定まるため、 dp[m][l][r] == dp2[m][l+r] * binom(l+r, l) です（binom は二項係数）。

dp2[i][j] は、以下のように計算できます。

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

これで、\(O(nm)\) でこの問題を解くことができました。これは問題の制約のもとで十分高速です。

C++による実装例

Pythonによる実装例