ヒント → https://atcoder.jp/contests/arc149/editorial/4868

---

[1] 問題の言い換え (1)

問題では，ソート対象となる区間をひとつずつ動かしていますが，ソート対象となる区間が左端から始まるように座標変換すれば，次の操作を \(K\) 回繰り返す問題を解けばよいことが分かります．

操作：\((A_0, \ldots, A_{M-1})\) をソートしたあと，左方向に \(1\) つ cyclic shift する．

以下この形で問題を扱います．例えば入力例 1 の数列 \(A = (4,1,5,6,2,3)\) に対して操作を行うと，数列は次のように変化します：

\((4,1,5,6,2,3) \to (4,5,6,2,3,1) \to (5,6,2,3,1,4)\to (5,6,3,1,4,2) \to (5,6,1,4,2,3)\to (5,6,4,2,3,1)\)

---

[2] 問題の言い換え (2)

操作を左側 \(M-1\) 項と右側 \(N-M+1\) 項に分けて見ると，さらに理解しやすくなります．左側 \(M-1\) 項については \(1\) 回以上の操作を行うと必ず昇順に並ぶため，この部分は単に集合として扱うことにしましょう．

簡単のため \(L=M-1\), \(R=N-M+1\) と書くことにします．また，数列の左側 \(L\) 項からなる集合を 左側集合、右側 \(R\) 項からなる数列を 右側数列 と呼ぶことにします．

すると操作は次のように言い換えることができます．

\(L\) 要素の左側集合と，\(R\) 項からなる右側数列がある．操作では，まず右側数列の先頭の項を左側集合にうつし，次に左側集合の最小要素を右側数列の末尾にうつす．

初期状態	\(\{1,4\}\)	\((5,6,2,3)\)
1 回目	\(\{4,5\}\)	\((6,2,3,1)\)
2 回目	\(\{5,6\}\)	\((2,3,1,4)\)
3 回目	\(\{5,6\}\)	\((3,1,4,2)\)
4 回目	\(\{5,6\}\)	\((1,4,2,3)\)
5 回目	\(\{5,6\}\)	\((4,2,3,1)\)

---

[3] \(K=R\) の場合への帰着

本問題は，\(K=R\) の場合，つまり右側数列のどの項もちょうど \(1\) 度ずつ左側集合への挿入対象となるまで操作を行う場合に帰着して解くことができます．

\(K < R\) の場合，つまり一度も左側集合への挿入対象とならない項が存在する場合には，単にそのような項を無視して問題を解けばよいです．

\(K > R\) の場合を考えます．\(R\) 回操作を行った時点で，左側集合は大きい数から \(L\) 個をとったもの \(\{R+1, \ldots, N\}\) になります．そのあとは左側集合に挿入された数がそのまま左側集合から削除されるため，\(R\) 回目以降の操作は単に右側数列の cyclic shift となります．このことから \(K\) 回操作を行った状態から \(R\) 回操作を行った状態を復元できるため，\(K>R\) の場合の問題も \(K=R\) の問題へ帰着可能です．

---

[4] 数え上げ

\(K\) 回操作後の状態が，左側集合 \(\{R+1, \ldots, N\}\)，右側数列 \((x_1, \ldots, x_R)\) であるとします（左側集合がこの形でない場合には答は \(0\) です）．これが成り立つような初期状態 \(\{a_1, \ldots, a_L\}, (b_1, \ldots, b_R)\) を数え上げましょう．

まず，\(x_{i-1} > x_{i}\) ならば \(b_i = x_i\) であることが必要です．これは，\(i-1\) 回目の操作終了時点で左側集合の要素はすべて \(x_{i-1}\) より大きいためです．

さらにこのような \(b_i, x_i\) は除外して考えることで，\((x_i)\) が単調増加である場合に帰着できます．このとき \(a_i, b_j\) に関する条件は

• \(a_1, \ldots, a_L, b_1\) のうちいずれかが \(x_1\) に等しい．
• \(a_1, \ldots, a_L, b_1, b_2\) のうちいずれかが \(x_2\) に等しい．
• \(a_1, \ldots, a_L, b_1, b_2, b_3\) のうちいずれかが \(x_3\) に等しい．
• \(\vdots\)

と言い換えることができます．この場合 \(x_1, x_2, \ldots\) の順にそれがどの \(a_i, b_j\) と一致しているかを考えることで，初期状態は \((L+1)^{R}\) 通りであることが分かります．「左側集合」は元の問題では単に数列であるので，これに \(L!\) をかけたものが答となります．

---

解答例

https://atcoder.jp/contests/arc149/submissions/35220965