Restricted Permutations | CS Academy #40 (Div. 2 only)

値1からNまで順にみていき、もともと空の配列のどこかに1つずつ挿入する。

今、1~K-1の値からなる順列のどこかにKを挿入したい。Kが挿入できる位置は、K-1の位置だけに依存する。(K+1は順列内にはないので）

よって、以下のようなDPを考えればよい。

dp[i][j]

= 値iまで含む順列であって値iがjにあるような順列の数