AGC005 D ~K Perm Counting 別解(箱根駅伝DP)

AGC005D ~K Perm Counting を解きました。初めて箱根駅伝DPを使いました。

問題

AtCoder Grand Contest 005 D ~K Perm Counting
問題リンク：https://atcoder.jp/contests/agc005/tasks/agc005_d

条件がすべて $|a_i-i| \ne 1$ の形になるように帰着する。

　数列 $a$ の添字を次のように置き換えます。数列の値も同じように置き換えます。

$1,K+1,2K+1, \cdots ,2,K+2,2K+2, \cdots ,3,K+3,2K+3 \cdots $ を $1,2,3, \cdots $ に置き換える。

このようにすると、もともと添字の差が $K$ だった要素の組が隣り合うようになります。

　問題は次のように変化します。（これを新しい問題とします。）

　数列 $S$ が与えられます。下の条件を満たす長さ $N$ の順列 $a_1,a_2, \cdots a_N$ を数え上げてください。

箱根駅伝DPのテーブルを $4$ 倍した DP で解ける。

　「箱根駅伝DP」は、 $(1,2, \cdots ,N)$ と $(1,2, \cdots ,N)$ のマッチングを数え上げるときに用いて、

というテーブルを持つDPを指します。(参考^[1])

　新しい問題の、条件が関わる部分の遷移に注目します。

　通常の箱根駅伝 DP に加えて、「直前の要素 ( $2$ 個あります ) それぞれがマッチングに使われたか」という情報を添字に持ちます。使われていない場合、次の遷移でこの要素とのマッチングはできないので、遷移のときの倍率が $1$ 小さくなります。

　条件が関わらない部分は、通常の箱根駅伝DPと同様に遷移すればよいです。

遷移の倍率をわかりやすくするため、 DP の添字の $k$ は「マッチングしていないペアが$k$ 個の場合」を表します。