条件を満たすかどうかについて考える場合、 pi はその偶奇にしか興味がありません。
以下のような数列の個数を求めることが出来れば、それに ⌊N/2⌋!×⌈N/2⌉! を掛けることによって答えが求まります。
- 長さ が N であり、各要素が 0,1 のどちらかであり、1 の個数が ⌈N/2⌉ であり、条件に違反しない
これは以下のようなdpで求めることが出来ます。
- dp[i][j]= i 項目まで決めて、 1 が j 個出てきて、今のところ条件に違反しないものの個数
答えは dp[N][⌈N/2⌉]×⌊N/2⌋!×⌈N/2⌉! です。