P3067 [USACO12OPEN] Balanced Cow Subsets G

我们定义一个奶牛集合 $S$ 是平衡的，当且仅当满足以下两个条件： - $S$ 非空。 - $S$ 可以被**划分**成两个集合 $A,B$，满足 $A$ 里的奶牛产奶量之和等于 $B$ 里的奶牛产奶量之和。划分的含义是，$A\cup B=S$ 且 $A\cap B=\varnothing$。 现在给定大小为 $n$ 的奶牛集合 $S$，询问它有多少个子集是平衡的。请注意，奶牛之间是互不相同的，但是它们的产奶量可能出现相同。

第一行一个整数 $n$，表示奶牛的数目。 第 $2$ 至 $n+1$ 行，每行一个数 $a_i$，表示每头奶牛的产奶量。

输出一个数表示方案总数。 ### 样例解释 共存在三种方案。集合 $\{1,2,3\}$ 可以划分为 $\{1,2\}$ 与 $\{3\}$；集合 $\{1,3,4\}$ 可以划分为 $\{1,3\}$ 与 $\{4\}$；集合 $\{1,2,3,4\}$ 可以划分为 $\{1,4\}$ 与 $\{2,3\}$，共 $3$ 种子集。

对于全部数据，保证 $1\le n\le 20$，$1\le a_i\le 10^8$。