いろはちゃんコンテスト Day 2 J - ヌクレオチド

• 問題
• AC

$N$が偶数の場合を考える。左右の$N/2$文字をそれぞれ$L, R$とすると$R$は$L$の反転になる。つまり、$L$の中で転倒$A_i > A_j, i < j$が起こっているとき、$R$の対応する位置では$A_{i'} < A_{j'}$となる。$L,R$をあわせると、$A_i = A_j$である$i, j$以外は1回ずつ転倒を数えていいことになる。つまり、$L$に$0$が$z$個含まれるとすると、$A_i = A_j = 0$なる組が$\binom{z}{2}$個、$A_i = A_j = 1$なる組が$\binom{N/2-z}{2}$個含まれるので、$L$の並べ方全体からこれらを引けば（$L$内と$R$内の）転倒の総数が$\binom{N/2}{z}-\binom{z}{2}-\binom{N/2-z}{2}$と数えられる。あとは$L$内の$1$と$R$内の$0$による転倒を足して

$$\binom{N/2}{z}-\binom{z}{2}-\binom{N/2-z}{2} + (n/2-z)z = K$$

$L$に$0$が$z$個含まれるときにはこの等式が成立していなければならないことになる。式を整理すると$2z^2 -Nz + K = 0$となって、この二次方程式の整数解は高々2つなので、2つの解について数列の総数を求めればよい: $\binom{N/2}{z_1} + \binom{N/2}{z_2}$

$N$が奇数の場合についても、例えば中央が$0$と決めて同様の議論をすればよい。（対称性により、中央が$1$の場合も同数の列がある。）