CF963E Circles of Waiting（高斯消元，主元法）

CF963E Circles of Waiting

平面直角坐标系上有一个点，开始在 \((0, 0)\)，每秒钟这个点都会随机移动：如果它在 \((x, y)\)，下一秒它去 \(4\) 个方向的概率为 \(p_0, p_1, p_2, p_3\)，各次移动互不关联。求出这个点移动至距离原点欧几里得距离 \(> R\) 的点的期望步数。\(R \le 50\)。

CODE

把这个圆每行第一个格子作为主元。一列一列做，每次通过已经求出的格子 \((x, y)\) 的主元多项式求出下一行 \((x, y + 1)\) 的多项式。最后对主元做高斯消元。时间复杂度 \(\Theta(N ^ 3)\)。

错因：高斯消元 \(\neq\) 行列式。消成右上三角矩阵后要往前消成对角线。