将答案序列看作一条平面上由 $(n,m)$ 到 $(0,0)$ 的路径，某次答案为 Yes 则往左走，否则往下走。于是每道题都与某条边一一对应；而每次答题人所面对的状态，即目前两种答案分别剩 $x,y$ 个，则与平面上某个点 $(x,y)$ 一一对应。

那么答题人的最优策略是显然的，当目前在直线 $y=x$ 以下时，猜答案为 Yes；当目前在直线 $y=x$ 以上时，猜答案为 No；当恰好落在直线上时，随便怎么猜，猜对的概率均为 $\frac12$。

我们来考察某种答案序列所对应的路径，假设 $n\ge m$，将整条路径在所有 $x=y$ 点处断开，形成多个段。

$n>m$ 时第一个段一定在 $y=x$ 下，这个段中每次询问都会得到回答 Yes，其中所有向左走的路径对应的问题是正确的，于是这段中答对问题的数量等于这部分路径的 $x$ 坐标跨度。

其余段中，除了段首第一个询问恒定有 $\frac12$ 的概率是正确的，其余所有边朝向直线 $y=x$ 的问题都是回答正确的。而这些段中起点终点均在 $y=x$ 上，所以 $x$ 坐标跨度等于 $y$ 坐标跨度，所以这些段中回答正确的问题数量期望都等于 $x$ 坐标跨度加 $\frac12$。

于是总答案等于 $n+\frac k2$，其中 $k$ 为回答的第二类段的期望数量，等于该路径与直线 $y=x$ 的交点个数减一。

那么对于每个点 $(x,x)$ 计算路径经过它的概率，计算相应贡献即可。

[USACO10HOL] Driving Out the Piggies G

从节点 $0$ 出发，在无向图上游走，在每个节点有 $p$ 的概率终止，否则等概率走向相邻节点。

设 $f_{i,u}$ 为 $i$ 时刻之前随机游走过程未终止，而 $i$ 时刻小 P 在点 $u$ 的概率。

而 $0$ 时刻在点 $1$，于是 $f_{0,u}=[u=1]$。

而第 $i$ 时刻（$i>1$）的情况可以表示为

$$\displaylines{f_{i,u}=\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|} }$$

于是最终停留在点 $u$ 的概率为

$$\displaylines{\sum_{i=0}^\infty pf_{i,u}=p\sum_{i=0}^\infty f_{i,u} }$$

令

$$\displaylines{\begin{aligned} g_u&=\sum_{i=0}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty f_{i,u}\\ &=f_{0,u}+\sum_{i=1}^\infty\sum_{v\in N(u)}\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\sum_{i=1}^\infty\frac{(1-p)f_{i-1,v}}{|N(v)|}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\sum_{i=0}^\infty f_{i,v}\\ &=f_{0,u}+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v \end{aligned} }$$

据此我们可以列出关于 $g$ 的方程组

$$\displaylines{\begin{cases} g_0+\sum_{v\in N(0)}\frac{1-p}{|N(v)|}\cdot g_v=1\\ g_u+\sum_{v\in N(u)}\frac{1-p}{|N(v)|}\cdot g_v=0&(u\neq 0) \end{cases} }$$

然后使用高斯消元求解。

[HNOI2013] 游走

从节点 $0$ 出发，在无向图上游走，等概率走向相邻节点，到 $t$ 点结束，求经过每条边的期望次数。

记 $N'(u)=N(u)\setminus\{t\}$。

设事件 $A_{i,u}$ 为第 $i$ 个时刻在点 $u$，$B_{i,v,u}$ 为 $i-1$ 时刻到 $i$ 时刻间由点 $v$ 转移到了点 $u$。显然有 $P(A_{0,u})=[u=0]$。

不难发现，对于 $v\in N'(u)$ 有

$$\displaylines{P(A_{i,u}B_{i,v,u})=P(A_{i-1,v}B_{i,v,u})=P(B_{i,v,u}|A_{i-1,v})P(A_{i-1,v})=\frac{P(A_{i-1,v})}{|N'(v)|} }$$

由全概率公式，易得

$$\displaylines{P(A_{i,u})=\sum_{v\in N'(u)}P(A_{i,u}B_{i,v,u})=\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|} }$$

设 $f_u$ 为经过 $u$ 的期望次数，由期望的线性性可得

$$\displaylines{\begin{aligned} f_u&=\sum_{i=0}^\infty P(A_{i,u})\\ &=P(A_{0,u})+\sum_{i=1}^\infty\sum_{v\in N'(u)}\frac{P(A_{i-1,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\sum_{i=0}^\infty\frac{P(A_{i,v})}{|N'(v)|}\\ &=[u=0]+\sum_{v\in N'(u)}\frac{f_v}{|N'(v)|} \end{aligned} }$$

由此可列出线性方程组，通过高斯消元解得答案。

期望 DP，只维护合法的状态。

每次询问暴力做矩阵快速幂会超时，所幸，对于所有询问，要做快速幂的矩阵是相同的，并且我们只需要向量乘矩阵幂后的结果。所以可以预处理出快速幂所需要的中间量，即 $A^{2^k}$ 处的取值，快速幂就只需 $\log n$ 次向量乘矩阵，时间开销由 $O(Tm^3\log n)$ 优化为 $O(m^3\log n+Tm^2\log n)$。