洛谷原题链接：P3067 [USACO12OPEN] Balanced Cow Subsets G
题意：
有 nnn 个数，第 iii 个数大小为 M(i)M(i)M(i)，要从 nnn 头奶牛中选出一个奶牛子集 SSS 使得 SSS 能够被划分成两个子集 LLL 和 RRR，其中 LLL 子集内的奶牛总产量等于 RRR 子集内的奶牛总产量。问有多少个 SSS 符合条件。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
翻译：
有 nnn 个数构成多重集 MMM，第 iii 个数为 M(i)M(i)M(i)，从中选出一个子集 SSS 使得 SSS 能够划分为两个子集 LLL 和 RRR，使得 LLL 和 RRR 内元素之和相等，求 SSS 的个数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
暴力思路：
最简单的想法必然是暴力——直接深搜，每次要么把当前奶牛加入 LLL 子集，要么加入 RRR 子集，要么都不加入，最终判断 LLL 子集内的奶牛总产量是否等于 RRR 子集内的奶牛总产量即可
该版本の代码：
小优化：如果和较小的那个子集加上剩下所有的奶牛都没办法达到和较大的那个子集，则这种方案不管怎么继续往下选择，都不可能得到一个平衡的子集 SSS，因此剪枝
最坏时间复杂度：O(3n)=O(320)O(3^n)=O(3^{20})O(3n)=O(320) 明显会超时
预计得分：≤30pts\leq30pts≤30pts（洛谷实测，得分 19pts19pts19pts）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
优化思路：
原本直接一个递归暴力枚举所有情况，思路可行，也很容易想到，但是太容易超时。
那么，不妨把原数组一分为二，从当中切开分别处理前半段和后半段。这便是折半搜索。
这样子的话，时间复杂度直接砍成了 O(2×3n2)=O(2×310)O(2\times3^\frac{n}{2})=O(2\times3^{10})O(2×32n )=O(2×310)，明显不会超时（除非你在分别递归完之后处理不当）
递归操作同上，只是到了最后一层的时候对数据的处理需要做修改。
因为现在一分为二，你在对前半部分递归的时候无法知晓后半部分的数据处理完之后到底怎样。因此，你需要对前半部分的选择进行记录并保存在合适的容器里。
我这边采用状态压缩的方式存储每一次选择的结果，因为这边状态只有选(000)和不选(111)两种操作，这样我就不需要再用数组来保存每个位置的选择，而且方便保存每次的状态。
然后我是考虑利用一个哈希表unordered_map，就叫它 *** 吧，毕竟是difference单词的首字母，d[x]d[x]d[x] 表示所有 R−L=xR-L=xR−L=x 的状态，主要是为了记录下所有差值为 R−LR-LR−L 的选择方案，以便于后续答案统计。
（当然，如果你有更好的方案，完全可以不按照我这种方法写）
把前半部分保存下来就简单很多了，后半部分的递归思路同上，只是注意要从一半的位置（而非数组的开头）开始。
后半部分到了最后一层之后，便需要从当前状态开始查找并统计答案。
假设前半部分放入 LLL 子集的和为 L1L_1L1 ，放入 RRR 子集的和为 R1R_1R1 ，后半部分放入 LLL 子集的和为 L2L_2L2 ，放入 RRR 子集的和为 R2R_2R2 ，
为了保证 L=RL=RL=R，即 L1+L2=R1+R2L_1+L_2=R_1+R_2L1 +L2 =R1 +R2 ，调整得 R1−L1=L2−R2R_1-L_1=L_2-R_2R1 −L1 =L2 −R2 。
由于在前面的哈希表中是按照 R1−L1R_1-L_1R1 −L1 存储的所有选择方案，那么在后半部分的递归到最后一层时，只需要访问 d[L−R]d[L-R]d[L−R] （或者说 d[L2−R2]d[L_2-R_2]d[L2 −R2 ]）就能够查找到所有和当前选择能够组合出平衡子集 SSS 的方案。
不过，有一个细节需要注意：你不能直接ans+=d[L-R].size()，因为可能会有重复的情况。还需要开一个标记数组vis，vis[state]=1说明 statestatestate 这个选择的状态已经有了，不能重复计数。
至于为什么会有重复计数，我举一个例子：
奶牛产量为 {1,3,2,4}\{1,3,2,4\}{1,3,2,4}，前半部分我把 111 放入 LLL，把 333 放入 RRR，后半部分我把 222 放入 RRR，把 444 放入 LLL，则 S={1,3,2,4}S=\{1,3,2,4\}S={1,3,2,4}
但我如果前半部分把 111 放入 RRR，把 333 放入 LLL，后半部分我把 222 放入 LLL，把 444 放入 RRR，则 S={1,3,2,4}S=\{1,3,2,4\}S={1,3,2,4} 和上面一样，
但在程序中它们被分别放在 d[3−1]d[3-1]d[3−1] 和 d[1−3]d[1-3]d[1−3] 中，如果直接ans+=d[L-R].size()会让同一个 SSS 被统计两遍，与题意不合。
最终版本の代码：
时间复杂度：约 O(3n2)=O(310)O(3^\frac{n}{2})=O(3^{10})O(32n )=O(310)
预计得分：100pts100pts100pts
ACGO&洛谷实测：均可AC
解锁成就：时空双修（截止到作者提交的时刻，作者的代码时间和空间均超过了 100%100\%100% 的用户）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
附：
状压：利用二进制，将 010101 状态压缩为一个二进制下的整数。
操作：二进制下，从右往左第 iii 位为 111 表示数组第 iii 个元素被选择，反之则是不被选择。
优势：可以直接使用位运算来操作，消耗时间少，且能够作为数组和其他 STL\tt{STL}STL 容器的下标和值。
标记数组 vis 具体大小：220=10485762^{20}=1048576220=1048576，覆盖了 000 到 220−12^{20}-1220−1 所有状态。
示例代码中开的大小为vis[1050000]完全足够。
