Prefix Permutation

条件を満たすかどうかについて考える場合、 $p_i$ はその偶奇にしか興味がありません。
以下のような数列の個数を求めることが出来れば、それに $\lfloor N/2 \rfloor ! × \lceil N/2 \rceil !$ を掛けることによって答えが求まります。

• 長さ が $N$ であり、各要素が $0,1$ のどちらかであり、$1$ の個数が $\lceil N/2 \rceil$ であり、条件に違反しない

これは以下のようなdpで求めることが出来ます。

• $dp[i][j]=$ $i$ 項目まで決めて、 $1$ が $j$ 個出てきて、今のところ条件に違反しないものの個数

答えは $dp[N][\lceil N/2 \rceil]×\lfloor N/2 \rfloor ! × \lceil N/2 \rceil !$ です。