这题绝大多数题解理论复杂度都是错的。。。只是根本 hack 不掉。。。

题解区普遍的代码思路如下：

• 把前一半的组合的值用 umap 什么的存下来；
• 枚举后一半的组合，再枚举前面对应值的 vector，统计答案，然后认为时间复杂度是 $\mathcal O(3^\frac n2)$ 或者什么的。

但是理论上，有一种最坏情况：所有前一半组合的和都一样，而所有后一半组合的和也是这个值，那么这样的代码就会执行 $3^\frac n2$ 次「枚举一个 $3^\frac n2$ 长度的 vector」的操作，你就会发现它爆飞了。

但是……实际上这样的数据几乎只有全 $0$……但是数据范围写了 $a_i\ge 1$……

即使允许 $a_i=0$ 那么把全 $0$ 判掉似乎也很难卡。

所以最强的 hack 大概是全 $1$ 之类的。虽然程序仍然可能跑得飞快，但是你只要加个 cnt 就会发现它循环已经跑了几亿次。（当然全 $0$ 效果更显著，只是它不符合数据范围罢了。）

问题就是，这样的错解，是怎么大量出现在题解区（而且个人认为极其误导人）的？

其实修起来也很简单，你直接跑完前一半对每个 vector 去个重，那么它们的长度就至多是 $2^\frac n2$ 的了，总复杂度 $\mathcal O(6^\frac n2)$，大概 $6\times 10^7$ 的样子。

（实际上如果让前一半长度为 $B$，那么可以分析出 $\mathcal O(3^B+3^{n-B}2^B)$，取 $B=14$ 可以做到大概 $1.67\times 10^7$ 的理论复杂度。当然也有可能带个 $\log$ 或者大常数什么的。）

当然如果有理论复杂度更优的做法也可以分享一下。