AGC065-B Erase and Insert（Difficulty: 2193）の解説です．
問題
\left(0,\ldots,N-1\right) の順列 P が与えられる．また，Q=\left(0,\ldots,N-1\right) とする．
Q に対し以下の操作を i=0,\ldots,N-1 の順に行う：
- Q から i を削除し，Q に i を 1 個自由な場所に挿入する
N 個の操作が終わったあとに P, Q が等しくなるような操作方法の個数を 1000000007 で割ったあまりを求めよ．
制約
- 1\leq N\leq 5000
解答
操作を逆順に考えます．P に問題と同様の操作を i=N-1,\ldots,0 の順に施して Q に移す操作方法を数える問題になります．
これをDPで解きます．\mathrm{dp}[i][j]=（i までの操作を行い，i が位置 j にある操作方法の個数）とします．\mathrm{dp}[N][N]=0 と初期化し，i の降順でテーブルを埋めます．求める答えは \mathrm{dp}[0][0] です．
\mathrm{dp}[i][j]から配る遷移について考えます．i が位置 j にある状態から i-1 を削除すると，i の位置は j-1 または j となります．ここで， i 未満の要素からなる部分列を考えます．操作順を考慮すれば，この時点で i より左には i より小さい整数のみが j 個あるので，部分列において i は（部分列には含まれないものの）位置 j-1 と j の間にあります．一方で，部分列の要素にはそれまでに一度も操作が行われていないので， x=（P の要素のうち i-1 未満かつ i-1 より手前にあるものの個数）とすると，i-1 は部分列の位置 x にあります．したがって，x<j ならば i-1 の方がより左側に位置するため削除後の i の位置は j-1 となり，そうでなければ j となります．
その後 i-1 を挿入する場所として，i より左にある任意の場所を選ぶことができます．つまり，x<j ならば \mathrm{dp}[i-1][0],\ldots,\mathrm{dp}[i-1][j-1] に，そうでなければ \mathrm{dp}[i-1][0],\ldots,\mathrm{dp}[i-1][j] に \mathrm{dp}[i][j] の値を加えればよいです．
累積和を用いると一つの i に対する処理が \mathrm{O}(N) 時間で実行できるので，全体で \mathrm{O}(N^2) 時間となります．よって解けました．
実装例（C++, 176 ms）