考虑将答案转化为期望，最后乘上 $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)$。

简要题解：

先手推一波式子：

$$f(i,m)=a^{m-1}\times f(i,1)+\frac{a^{m-1}-1}{a-1}\times b$$

再次展开，得：

$$\begin{bmatrix}f(i,m) & 1\end{bmatrix}\times \begin{bmatrix}a^{m-1}\times c & 0\\a^{m-1}\times d+\frac{a^{m-1}-1}{a-1}\times b & 1\\\end{bmatrix}=\begin{bmatrix}f(i+1,m) & 1\end{bmatrix}$$

高精度十进制快速幂即可。

注意特殊处理 $a=1$ 的情况。

显然的贪心思路：让被经过期望次数多的边的编号尽量小。但是这题 $m$ 可能为 $10^5$ 级别，不能对边进行求解。

考虑求出每个点的期望经过次数，设其为 $f_i$，令点 $i$ 的度数为 $deg_i$。

则有:

$$f_1=(\sum\limits_{(1,v)\in E\land v\neq n} \frac{f_v}{deg_v})+1,f_i=\sum\limits_{(i,v)\in E\land v\neq n}\frac{f_v}{deg_v}(1\lt i\lt n)$$

$v\neq n$ 的原因是，一旦 $v=n$，就走到 $n$ 了，肯定不可能再走回 $i$。

因为有后效性，所以将其列成矩阵进行高斯消元求解。

则：

$$\forall (u,v)\in E,g(u,v)=\frac{f_u}{deg_u}+\frac{f_v}{deg_v}$$

其中 $g(u,v)$ 表示边 $(u,v)$ 被经过的期望次数。

注意特判 $u\neq n,v\neq n$，原因同上。

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

搜不到题解啊，自己随便写一篇玩。

如果直接求亮灯数的期望 $E$，这是不好处理的，因为我们不可能把所有灯的亮暗同时放入到状态中。

不妨换一个角度，去分别考虑每个灯最终的状态。考虑计算坐标$(x,y,z)$的灯最终亮着的概率 $P_{x,y,z}$，那么它有 $P_{x,y,z}$ 的概率给答案贡献 $1$，即 $E=\sum{p_{x,y,z}}$。

接下来的问题是如何计算 $P_{x,y,z}$。

首先考虑任选 $A,B$ 能包含 $(x,y,z)$ 的概率（以下简记为 $P_{cr}$），不难得到 $P_{cr}=\frac{2x(n-x+1)-1}{n^2}\frac{2y(m-y+1)-1}{m^2}\frac{2z(p-z+1)-1}{p^2}$。

一种直接的想法是DP。设 $f_{i,x,y,z,0/1}$ 表示 $i$ 次操作后，$(x,y,z)$ 暗/亮的概率，转移显然：

$f_{i,x,y,z,0/1}=P_{cr}f_{i-1,x,y,z,1/0}+(1-P_{cr})f_{i-1,x,y,z,0/1}$

第一维可以滚，时间复杂度$O(nmpk)$，寄了。

仔细想想其实不用DP，一盏灯最终是亮的，那么它可能被操作 $1,3,5,...$ 次，即 $P_{x,y,z}=val(1)+val(3)+val(5)+...$，其中 $val(i)$ 表示恰好被操作 $i$ 次的概率。

$val(i)$ 怎么算？其实就是从 $k$ 次操作中选出 $i$ 个包含它，即 $val(i)=C^{i}_{k}P_{cr}^i(1-P_{cr})^{k-i}$。

整理一下，$P_{x,y,z}=C^{1}_{k}P_{cr}(1-P_{cr})^{k-1}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+...$

经典二项式定理。

$[(1-P_{cr})+P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}+C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}+C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\alpha)$

$[(1-P_{cr})-P_{cr}]^k=C^{0}_{k}(1-P_{cr})^{k}-C^{1}_{k}P_{cr}^1(1-P_{cr})^{k-1}+C^{2}_{k}P_{cr}^2(1-P_{cr})^{k-2}-C^{3}_{k}P_{cr}^3(1-P_{cr})^{k-3}+... (\beta)$

于是$P_{x,y,z}=\frac{\alpha-\beta}{2}=\frac{1-(1-2P_{cr})^k}{2}$

这样就整完了。时间复杂度$O(nmp\log k)$，其中$\log k$为快速幂。