\(O(N 2^N)\) 時間のbitDPについて補足します。
以下、添字を0始まり(0-indexed)で扱います。

本問のbitDP部分を抜き出すと、およそ次のような問題となります。
(説明のため、分割数の最大値だけでなく余りの最大値も考えることにします)

---

部分問題1

要素数 \(N\) の多重集合 \(A = \{A_0, A_1, ･･･, A_{N-1}\}\) を与えます。
あなたは \(0\) 回以上、次の操作を行うことができます:

• 要素の総和が \(0\) となるような \(A\) の非空な部分集合を選び、 \(A\) から削除する。

操作を行える最大回数を \(X\) 、そのとき最終的に残る要素数の最大値を \(Y\) とします。 \((X, Y)\) を順に出力してください。

入力例: \(N = 7, A = \{1, 2, 2, 3, 5, -4, -7\}\)
出力例: \(X = 2, Y = 1\)

• 例えば以下のように操作したとき、操作回数は \(2\) 回・操作後に残る要素数は \(1\) 個です。

  • \(1\) 回目の操作では \(\{2, 5, -7\}\) を選び、 \(A\) から削除する。
    \(A = \{1, 2, 3, -4\}\) となる。
  • \(2\) 回目の操作では \(\{1, 3, -4\}\) を選び、 \(A\) から削除する。
    \(A = \{2\}\) となる。

---

これは EDPC-U Grouping のような \(O(3^N)\) の部分集合DPを行うことで \(N \leq 18\) 程度までなら解けますが、本問の \(N \leq 20\) の制約下では実行時間制限内に間に合わせるのは困難です。

次に、部分問題2を考えます。

---

部分問題2

要素数 \(N\) の多重集合 \(A = \{A_0, A_1, ･･･, A_{N-1}\}\) を与えます。
あなたは以下の順に操作を行います:

• \(A\) を好きな順に並べて数列 \(B = [B_0, B_1, ･･･, B_{N-1}]\) を作る。
• 先頭(\(B_0\) の直前)に、必ず仕切りを \(1\) 枚入れる。
• \(i = 0, 1, ･･･, N - 1\) の順に見ていき、
  • \(B_0, B_1, ･･･, B_i\) の総和が \(0\) なら、 \(B_i\) の直後・ \(B_{i+1}\) の直前に仕切りを \(1\) 枚入れてもいい(入れなくてもいい)。
  • 総和が \(0\) でないなら、仕切りは入れない。

操作後の仕切りの枚数を \(M+1\) 枚とすると、操作後の数列 \(B\) の区間はちょうど \(M\) 個の「分割」と高々 \(1\) 個の「余り」に分類できます。

• 「分割」: 両側を仕切りで挟まれた区間のこと。区間総和は必ず \(0\) となる。
• 「余り」: 片側にのみ仕切りがある区間のこと。

「分割」の個数の最大値を \(X\) 、そのときの「余り」の要素数の最大値を \(Y\) とします。 \((X, Y)\) を順に出力してください。

入力例: \(N = 7, A = \{1, 2, 2, 3, 5, -4, -7\}\)
出力例: \(X = 2, Y = 1\)

• \(B = [2, 5, -7, 1, 3, -4, 2]\) と並び替えた後、仕切りを|の文字で表して
  \(B\) = | 2, 5, -7 | 1, 3, -4 | 2
  となるように挿入します。このとき、

  • 「分割」は |2, 5, -7| と |1, 3, -4| の \(2\) 個です。
  • 「余り」は | 2 の部分で、要素数は \(B_6 = 2\) の \(1\) 個です。

---

ここで、部分問題1と部分問題2は同値です。
具体的には、部分問題1で削除する部分集合を削除順に\(S_0, S_1, ･･･, S_x\)、残った要素の集合を\(R\) としたとき、部分問題2において
\(B\) = | S_0 | S_1 | ･･･ | S_x | R
の順に仕切りと集合の要素を並べる操作に対応します。
(部分問題2の仕切りを入れる条件は累積和 \(0\) なので、「分割」の総和は必ず \(0\) となる点に注意してください)

以降は部分問題2を \(O(N 2^N)\) で解く方法を考えることにします。
重要な観察として、仕切りを入れる操作は「入れられる場所では必ず仕切りを入れる」としてかまいません。
仕切りを入れる条件は現在の累積和にのみ依存しており、仕切りを入れることで後続に悪影響を与えないからです。

これを踏まえて、 \(A\) の部分集合 \(S\) に対して \(DP[S] = (x, y)\) を次のように計算します。

• 定義: \(S\) の要素数を\(d\) とする。 \(S\) の要素を並べて \(B[0, d)\) に割り当てる方法のうち、
  • \(x\) : 「分割」の個数の最大値
  • \(y\) : そのときの「余り」の要素数の最大値
• 初期化: \(DP[∅] = (0, 0)\)
• 遷移: \(A_i\) を \(S\) に含まれない要素、 \(T = S ∪ {A_i}\) とする。
  • \(T\) の総和が \(0\) なら、「分割」を増やす: \(chmax(DP[T], (x + 1, 0))\)
  • \(T\) の総和が \(0\) でないなら、 「余り」を増やす: \(chmax(DP[T], (x, y + 1))\)
• 答え: \(DP[A]\)

この動的計画法は時間 \(O(N 2^N)\), 空間\(O(2^N)\) で行えるので、 \(N \leq 20\) の制約下でも実行時間制限内に間に合わせることが可能です。
元の問題は「余り」を持たなくていい代わりに、DPの経路復元の情報を追加したbitDPとみなせば同様に解けます。

提出例(Python Codon)