【CF963E】Circles of Waiting

foreverlasting

2019-10-12 15:25:04

Solution

[在这里也可以看呢](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)$的了。