CPSCO2019 Session3：F - Flexible Permutation
問題
解法
dp(i, a, b) := 1 ~ i までの全ての順列のうち，P_k > k となるような k の個数が a，P_k < k となるような k の個数が b である通り数
を考える．1 ~ i - 1 までの順列に新しく i を追加するとき，1 ~ i - 1 までの順列の末尾に i を追加し，追加した i をそのままにするか，任意の箇所と swap することで，1 ~ i の任意の順列を作ることが出来る．
ここで，swap する相手の箇所 k が P_k > k であるのか，P_k < k であるのか，P_k == k であるのかを場合分けして考える．swap する場合，P_k < i かつ P_i > k であるので，P_k > k であるとき，swap すると b が 1 増える．P_k < k であるとき，swap すると a が 1 増える．P_k == k であるとき，swap すると a と b がともに 1 増える．swap しない場合はともに変化しない．これらを DP の遷移とすると，
dp(i, a, b) = dp(i - 1, a, b - 1) * a + dp(i - 1, a - 1, b) * b + dp(i - 1, a - 1, b - 1) * (i - 1 - (a - 1) - (b - 1)) + dp(i - 1, a, b)
となる．O(N^3)．P_k == k となるような k を組み合わせ計算で決め打ちしておき，N == A + B とすることで O(N^2) に落とすこともできる．
解答
