CodeChef January Challenge 2020 - Chefina and Prefix Suffix Sums

• 問題
• AC

$0+suf_N = pre_1 + suf_{N-1} = pre_2+suf_{N-2} = ... = pre_N + 0$であることに注目する。この等式より、$pre_n = suf_n$は$入力全体の和/(N+1)$と一致しなければならない。この数が入力の中に2つなければ答えは$0$である。

さて、この2数を除いた$2(N-1)$個の数の中から残りを埋めることになる。まず、$a_i + b_i = S$になるような数の組み合わせを入力から探す。これらを

$$\{a_1, b_1\}, \{a_2, b_2\}, ..., \{a_k, b_k\}$$

とするとき、すべての$p$について$a_p$と$b_p$は入力の中に必ず同数存在しなければならない。逆に同数あれば、$pre_i = a_p$のとき$suf_{N-i} = b_p$（$pre_i = b_p$のとき$suf_{N-i} = a_p$）のように埋めていけば有効な列ができることになる。

$\{a_1, b_1\}, \{a_2, b_2\}, ..., \{a_k, b_k\}$がそれぞれ$c_1, ..., c_k$ペアあるとわかったら、あとは$\{a_1, b_1\}$から順に$N-1$個の位置を埋めていけばよい。つまり、

$$\binom{N-1}{c_1}2^{c_1} \cdot \binom{N-1-c_1}{c_2}2^{c_2} \cdot ... \cdot \binom{N-1-c_1-...-c_{k-1}}{c_k}2^{c_k}$$

が答えになる。$N-1$箇所の空きから$c_1$個選んで、さらに$a_1$と$b_1$のどちらを置くか選んで…… というイメージ。$a_i = b_i$のケースは$2$掛けがないので注意すること。

---

冒頭の事実に気づくのになんと二日かかってしまった。