考虑将答案转化为期望，最后乘上 $2^{n-1}$。

如果 $a_i$ 前是加号，有 $\frac{1}{2}$ 的概率，因此贡献为 $\frac{a_i}{2}$。

如果 $a_i$ 前是乘号，有 $\frac{1}{2}$ 的概率，贡献是 $\frac{a_i-1}{2}$ 乘以前 $i-1$ 个数的期望后缀乘积，这个可以递推算出来。

时间复杂度：$\mathcal O(n)$。