Cocoly1990's Blog

感谢@SharpnessV 大佬的不吝赐教。

我们可以手玩一下样例。

$(1+2+3)\times4=24$

$(4+1+2)\times4=28$

很显然这样并不怎么明显对吧，我们改成这样。

$(1+2+3)\times 2^2=24$

$(4+1+2)\times 2^2=28$

于是我们可以推出一个柿子。

$\mathcal{ans}=\sum\limits_{i=1}^nA_i\times2^{n-1}=\mathcal{sum}\times2^{n-1}$

很显然，$2$的幂快速幂处理，和部分在线处理，综合时间复杂度 $\mathcal{O}(Tn)$.

可为什么呢，我有一个对此命题十分优美的证明,可惜这里空白太小,我写不下了，其实我们可以这么看，对于集合内的每一个元素，我们都有选或不选两种选择，那么一个集合共有 $2^n$子集（包含空集）。又因为每个元素只有选或不选两种选择，所以每个元素在子集中出现的次数有 $2^{n-1}$。

于是就有了上式。