题解 CF963E Circles of Waiting

标签：Circles CF963E 题解 Waiting 3f 高斯消

令 \(f_{i,j}\) 表示 \((i,j)\) 走出以 \((0,0)\) 为圆心，半径为 \(R\) 的期望步数，显然所有在圆外的点 \((i,j)\) 满足 \(f_{i,j}=0\)。

有 \(f_{i,j}=p_1 f_{i-1,j}+p_2 f_{i,j-1}+p_3f_{i+1,j}+p_4 f_{i,j+1}\)。

这东西很套路，高斯消元就行，但状态数是 \(O(R^2)\) 的，复杂度 \(O(R^6)\)。

考虑主元法，只用 \(O(R)\) 个参数表示 \(O(R^2)\) 个点，尝试将每行最左边的 \(2R+1\) 个数拉出来当主元。

因为

\[f_{i,j}=p_1 f_{i-1,j}+p_2 f_{i,j-1}+p_3f_{i+1,j}+p_4 f_{i,j+1} \]

所以有

\[f_{i+1,j}=\dfrac{f_{i,j}-p_1 f_{i-1,j}-p_2 f_{i,j-1}-p_4 f_{i,j+1}}{p_3} \]

即

\[f_{i,j}=\dfrac{f_{i-1,j}-p_1 f_{i-2,j}-p_2 f_{i-1,j-1}-p_4 f_{i-1,j+1}}{p_3} \]

从左往右推即可。

对于每行右边第一个走出圆的点，利用其 \(f\) 值为 \(0\)，共可列出 \(2R+1\) 个方程，现在再去高斯消元就是 \(O(R^3)\) 的。

标签：Circles,CF963E,题解,Waiting,3f,高斯消
From： https://www.cnblogs.com/Terac/p/18038200