\(S=\sum_{i=1}^N P_i\) とします。\(S\) が奇数なら答えは明らかに \(0\) です。以降 \(S\) は偶数とします。

\(X\) を 「\(\{1 \dots N\}\) の部分集合 \(U\) のうち \(\sum_{i\in U}P_i = \frac{S}{2}\) を満たすものの個数」とします。

このとき、答えは \(X^2-2X\) になります。

\(X^2-2X\) になる理由

「各チームが空でもよい」として数えることにすると、\(X\) 通りの部分集合から独立に \(U,V\) の組を選ぶ \(X^2\) 通りの方法と、以下のチーム分けが一対一対応します。

• \(i \in U\) かつ \(i \in V\) のとき、人 \(i\) はチーム \(A\)
• \(i \notin U\) かつ \(i \notin V\) のとき、人 \(i\) はチーム \(B\)
• \(i \in U\) かつ \(i \notin V\) のとき、人 \(i\) はチーム \(C\)
• \(i \notin U\) かつ \(i \in V\) のとき、人 \(i\) はチーム \(D\)

このうち、\(U=V\) のときと \(U=\overline{V}\) のときのみ、空のチームが生まれます。（\(2X\) 通り）

\(X\) の求め方

\(X\) は簡単な部分和dpにより \(O(N (\sum{P_i}))\) で求めることができます。

余談

強さ \(p\) の人をチーム \(A,B,C,D\) に割り当てることをそれぞれベクトル \((p,0),(-p,0),(0,p),(0,-p)\) に対応させることを考えると、条件はベクトルの和が \(\vec 0\) になることと言い換えられます。

この \(4\) つのベクトルのうち \(1\) つを選ぶことを、\((\frac{p}{2},\frac{p}{2}),(-\frac{p}{2},-\frac{p}{2})\) のうち \(1\) つと \((\frac{p}{2},-\frac{p}{2}),(-\frac{p}{2},\frac{p}{2})\) のうち \(1\) つを独立に選んでその和を取ることに言い換えると、上記と同様の解法が得られます。