\(A\) のソートを除いて \(O(N)\) で解く方法です。

以下の問題が解ければ良いところまでは省略します。

\(s = 1, 2, ... , 2N\) 全てについて、以下の問題の答えを出力してください。

• \(|A| = 2N\) かつ \(A_{i} \in \{0, 1\} (1\leq i \leq N)\) かつ \(\sum A = s\) であるような全ての \(A\) に対する、Max Bracket Score の答えの総和を求めください。

\(s\) に対する上記の問題の答えは \(f(s)\) と表すことにします。

以下の問題の答えを \(g(s, t)\) とおくことにします。

以下の条件を全て満たす長さ \(2N\) の数列 \(A\) の場合の数を求めてください。

• \(\sum A = s\)
• \(A_{i} \in \{0, 1\} (1\leq i \leq N)\)
• \(A\) に対する Max Bracket Score の答えが \(t\) 以上

\(f(s) = g(s, 1) + g(s, 2) + \cdots g(s, N)\) が成り立つので、任意の \(s, t\) について \(g(s, t)\) が求まれば、任意の \(s\) に対する \(f(s)\) を求めることができます。

まず、任意の要素が \(\{0, 1\}\) に含まれるような長さ \(2N\) の数列 \(A\) に対する Max Bracket Score の答えは以下のように求められます。

長さ \(2N\) の数列 \(B\) を以下のように定めます。

• 任意の \(i\) に対して \(B_{i} = 2A_{i} - 1\)

また、整数 \(X\) を \(B\) の prefix sum の最小値とします。形式的には以下のように定めます。

• \(\displaystyle X = \min_{i = 0, 1, \dots , 2N}(B_{1} + B_{2} + \cdots B_{i})\)

このとき、答えは \(N - \lfloor\frac{1 - X}{2}\rfloor\) と表せる。

以上の結論から \(g(s, t)\) に対して以下が成り立ちます。

• \(\min(s, N) < t\) ならば \(g(s, t) = 0\)
• \(1\leq t\leq \min(s, N)\) ならば \(g(s, t) = \dbinom{2N}{s} - \dbinom{2N}{2t - s - 1}\)

よって、\(f(s)\) について以下が成り立ちます。

• \(\displaystyle f(s) = \min(s, N)\dbinom{2N}{s} - \sum_{i = -s + 1, - s + 3, \dots, 2\cdot\min(N, s) - s - 1}\dbinom{2N}{i}\)

\(1\) つ目の添字が \(2N\) であるような二項係数の累積和を \(2\) つ目の添字の偶奇それぞれについて前計算することで \(f(s)\) は定数時間で求めることができます。

実装例 pypy