∆ CF24D Broken robot - AC

设 $f_{i,j}$ 为从 $(i,j)$ 走到最后一排的期望步数，则有方程

$$f_{i,j}=\frac{1}{4}(f_{i,j-1}+f_{i,j+1}+f_{i+1,j}+f_{i,j})$$

直接高斯消元 $\Theta(nm^{3})$ 死有余辜。

仔细考虑一下，因为一个 $f_{i,j}$ 在同行的依赖项最多三个，所以一行中一共只有 $3$ 个未知数。

那么复杂度就成了 $\Theta(nm)$。

对了边界：

$$f_{i,1}=\frac{1}{3}(f_{i,1}+f_{i,2}+f_{i+1,1}) \\ f_{i,m}=\frac{1}{3}(f_{i,m}+f_{i,m-1}+f_{i+1,m})$$

特判 $m=1$。

∆ P3211 [HNOI2011]XOR和路径 - AC

异或的期望 $\neq$ 期望的异或（悲

按位考虑，设 $f_{u,0/1}$ 为 $1\rightarrow u$ 异或值第 $i$ 位 $0/1$ 的概率。

等一下非 $0$ 即 $1$。

之前作废）设 $f_{u}$ 为到 $u\rightarrow n$ 时，异或值的第 $i$ 位为 $1$ 的概率（后转期望），这个 $i$ 不需要带进状态里。

则有转移：

$$f_{u}=\begin{cases} \displaystyle \sum_{(u,v)\in E}\frac{1}{d_{u}}f_{v},\text{weight}(u,v)_{i}=1 \\ \displaystyle \sum_{(u,v)\in E}\frac{1}{d_{u}}(1-f_{v}),\text{weight}(u,v)_{i}=0 \\ \end{cases}$$

最后的答案就是对所有位求和。

Problem. 1 Junior - Formula

用 $m_{i,j}$ 表示答案，$a_{i,j}$ 表示原矩阵。

则方程为 $(m_{i,j}+m_{i-1,j}+m_{i+1,j}+m_{i,j-1}+m_{i,j+1}+a_{i,j})\operatorname{bitand}1=0$。

变下形高消即可。

Problem. 2 Junior / Senior - Formula

直接设概率做不来的样子。。。

问了一下懂行的人发现需要设期望。

设 $f_{u}$ 为节点经过 $u$ 的期望次数，设 $E$ 为边集，$d_{u}$ 表示节点 $u$ 的度。

$$f_{u}=(1-\frac{p}{q})\sum_{(u,v)\in E}\frac{1}{d_{v}}f_{v}$$

因为有环，所以需要高斯消元一下。

那么在每个节点爆炸的概率即为 $f_{u}\times\frac{p}{q}$。

总结一下，这道题告诉了我不仅是期望可以回归本质用概率搞，概率也可以用期望来整。

Problem. 3 Junior / Senior - Formula & Thinking

设 $f_{u,v}$ 表示同一时刻 Petya 在点 $u$，Vasya 在点 $v$ 的概率。

$$f_{u,v}=p_{u}p_{v}f_{u,v}+\sum_{(u,u')\in E}\sum_{(v,v')\in E}\frac{1-p_{u'}}{d_{u'}}\frac{1-p_{v'}}{d_{v'}}f_{u',v'}+\sum_{(u,u')\in E}p_{v}\frac{1-p_{u'}}{d_{v'}}f_{u',v}+\sum_{(v,v')\in E}p_{u}\frac{1-p_{v'}}{d_{v'}}f_{u,v'}$$

完了。