【CF963E】Circles of Waiting
foreverlasting
2019-10-12 15:25:04
[在这里也可以看呢](https://foreverlasting1202.github.io/2019/09/22/%E6%AF%AB%E6%97%A0%E6%84%8F%E4%B9%89%E7%9A%84%E5%81%9A%E9%A2%98%E8%AE%B0%E5%BD%95/)
高斯消元。
有个暴力的做法,令$f_{i,j}$为走到$(i,j)$的期望步数。
转移就是
$$
f_{i,j}=
\begin{cases}
p_1f_{i-1,j}+p_2f_{i,j-1}+p_3f_{i+1,j}+p_4f_{i,j+1}, & \text{if $i^2+j^2\leq R^2$ } \\
0, & \text{else}
\end{cases}
$$
这样暴力高消是$O(R^6)$的。
然后我们以每行第一个到源点距离小于等于$R$的点的$f$为主元,预处理出其他点到它的系数,直接高消。这样就是$O(R^3)$的了。