题意
你初始位于 ((0,0)) ，每次向上下左右四个方向走一步有确定的概率，问你什么时候可以走到 以 ((0,0))为圆心，(R) 为半径的圆外。
(Rle 50)
分析
- 暴力 (O(R^6)) 的高斯消元复杂度太高。
- 注意到本题在网格图上操作，假设我们从上至下从左至右依次给在圆内的点标号，那么对于当前点来说，相关的点(除了等式右边)和他的标号都不超过 (2R) 。所以高斯消元的时候只需要考虑向下的 (2R) 行和向右的 (2R) 列即可。
以前写的消成单位矩阵的方法是不可行的，因为向上消的操作会使上面的点所在的行中下面点那一列也存在。- 总时间复杂度 (O(R^4)) 。