Educational DP Contest / DP まとめコンテスト T - Permutation
解法
番目までの順列が完成しているときに、番目の数字を加えて条件を満たす数列を作成することを考えます。
長さの数列で、一番後ろにを選ぶときの並べ方の通り数
とします。
を求めるために、番目の数字と番目の数字の関係をもとに場合分けしていきます。
のとき
となっている、番目まで完成している任意の順列を1つ選びます。そして、この順列を少し組み換え、以上の数字にをしてあげると、これはを除き、からなる数列になっていて、なおかつこの数列は問題の条件を満たしています。
ということで、今作成した数列の最後尾にを付け加えると、これは長さの順列で、かつ問題の条件を満たしています。
これ以外で作成できる、長さで問題の条件を満たす順列は存在しません。上の操作と逆のことをすると元の順列を作成することができますが、逆操作を行う対象の順列が異なれば、逆操作後の順列も必ず異なるものになります。ので、長さ以下の順列を数え終えていることに反します。
とういことで、のとき、は未満になればよいので、
となります。
のとき
こちらも上と同様の手順を踏むことで、問題の条件を満たす順列が作成できます。これ以外に作成する方法がないので、結局はが以上になっていればよいです(上の操作では、以上の数にという操作を行っているので、がになっていても、条件を満たすことができることに注意します)。
ということで、
となります。
さて、あとはこのDPを行えばいいのですが、このままだと総和を取る操作で計算するのに時間がかかってしまいます。そこで、
とすると、
上の2つの遷移はそれぞれ、
となります。
ということで、このDPを行うと、答えは
を参照すればよいです。感想
証明まできっちり行ってから通すことができたので良かったのではないかなと思っています。
式変形も素直にできたのでよかったです。
思考の過程としては、割と上の解法をそのままたどるような形で、まずはある時点での数列を完成していた場合に、1つ長さを増やした数列を作成するにはどのようにすればいいだろうか、という部分から解法を思いつきました。