题解：P13320 [GCJ 2012 #1B] Equal Sums

测试点 1：直接枚举所有子集判断有没有两个不同子集的和相同即可，复杂度 $O(n2^n)$。

测试点 2：

考虑 $n = 500$，如果我们要从中选出 $k$ 个数，那么有 ${500 \choose k}$ 种选择。

$k = 6$ 时，有 ${500 \choose 6} = 2 \times 10^{13}$ 种不同的子集，而这些子集的最大值不会超过 $6 \times 10^{12}$，根据抽屉原理，一定会有子集和重复的子集。

我们每次随机取 $6$ 个数求和，直到出现重复的和为止即可。

这样做为什么不会 TLE？

$k = 6$ 的子集有 $2 \times 10 ^ {13}$ 个，我们从中选择 $x$ 个，选择的方案数有 ${2 \times 10^{13} \choose x}$ 种。

我们先假设所有 $k = 6$ 的子集和在 $[6, 6 \times 10 ^{12}]$ 范围内是均匀随机分布的，此时每个数的期望出现次数大概是 $\dfrac{10}{3}$。

那么不重复的选择方案就有 ${6 \times 10^{12} \choose x} \times (\dfrac{10}{3})^x$ 这么多种。

当 $x$ 足够大时，下面的方案数与上面的方案数的比值会几乎等于 $0$，也就是说不重复的选择方案几乎占所有选择方案的 $0\%$，那么这个时候选到的方案里就基本确定会有重复的了。

这个结论是建立在假设子集和均匀随机分布的基础上的。但实际上子集和并不一定均匀随机分布，那么这个结论还正确吗？

我们发现：均匀随机分布时不重复的选择方案数一定大于非均匀随机分布时不重复的选择方案数。为什么？

不会严谨证明，来一个不太严谨的证明：

设所有会出现的数构成了集合 $T$，其中每个数的出现次数为 $y_i$，不重复的选择方案数为：

我们知道 $\sum_{i \in T}y_i$ 是个固定值，根据基础不等式，显然所有 $y_i$ 相等时 $\prod_{i \in T}y_i$ 最大。也就是说：对于所有出现次数不为 $0$ 的数，当它们的出现次数全部相等时，方案数最多。

另外感性理解，如果所有出现次数不为 $0$ 的数出现次数都相等的话，显然 $|T|$ 越大选择时越不容易重复，也就是不重复的方案数越多。

根据这两条结论：所有出现次数不为 $0$ 的数出现次数相等时方案数最多；当所有出现次数不为 $0$ 的数出现次数都相等时，$|T|$ 最大时方案数最多。我们发现：这不就是均匀随机分布时的情况嘛。所以均匀随机分布时不重复的方案数最多，非均匀随机分布只会使不重复的方案数减少。

分母不变分子减少，那么概率只减不增，换言之就是选到重复的概率只会增大，所以不需要考虑这种情况了。

最终的 $x$ 的应该不会大于 $2 \times 10^7$。