A2207. 平衡奶牛子集
编程题
提高+/省选-
知识点
题目描述
农场主约翰拥有 N 头奶牛 （2 <= N <= 20），其中奶牛 i 每天产 M（i） 单位的牛奶 （1 <= M（i） <= 100,000,000）。FJ 希望简化每天挤奶的过程，因此他在牛舍中安装了一台全新的挤奶机。不幸的是，这台机器太敏感了：只有当牛舍左侧的奶牛的总产奶量与牛舍右侧的奶牛完全相同时，它才能正常工作！
如果可以将奶牛分为两组产奶量相等的奶牛，那么我们将其称为“平衡奶牛”。由于只有平衡的奶牛子集才能使挤奶机工作，FJ 想知道他的 N 头奶牛中有多少子集是平衡的。请帮他计算这个数量。
如果可以将奶牛分为两组产奶量相等的奶牛，那么我们将其称为“平衡奶牛”。由于只有平衡的奶牛子集才能使挤奶机工作，FJ 想知道他的 N 头奶牛中有多少子集是平衡的。请帮他计算这个数量。
输入格式
* 第 1 行：整数 N。
* 第 2..1+N 行：第 i+1 行包含 M（i）。
* 第 2..1+N 行：第 i+1 行包含 M（i）。
输出格式
* 第 1 行：奶牛的平衡子集数量。
输入输出样例
输入 #1
4 1 2 3 4
输出 #1
3
说明/提示
共存在三种方案。集合 {1,2,3} 可以划分为 {1,2} 与 {3}；集合 {1,3,4} 可以划分为 {1,3} 与 {4}；集合 {1,2,3,4} 可以划分为 {1,4} 与 {2,3}，共 3 种子集。