题解

思路

先允许队伍为空。

做法

把每个人分到 A、B 看成在第一个带符号和中取 $+P_i,-P_i$，分到 C、D 则在第二个带符号和中取 $+P_i,-P_i$。作变量替换后，每个人的四种贡献可以分解为两个独立的二选一贡献，因此若 $Q$ 表示把所有 $P_i$ 加正负号后总和为零的方案数，允许空队的答案就是 $Q^2$。正权值下 A 为空会强制 B 也为空，这样的方案有 $Q$ 个；C、D 同理，二者不可能同时为空，故所求为 $Q^2-2Q$。

$Q$ 等于选出元素和为总力量一半的子集数。总和为奇数时 $Q=0$；否则用一维 0/1 背包倒序转移并取目标和处的计数，最后代入公式。

复杂度

时间复杂度为 $O(N\sum P_i)$，空间复杂度为 $O(\sum P_i)$。