D. Broken robot
链接、
题意：
一个方格，从(x,y)出发，等价的概率向下，向左，向右，不动。如果在左右边缘上，那么等价的概率不动，向右/左，向下。走到最后一行即结束。求期望结束的步数。
分析：
因为不能往上走，所以行与行之间存在转移，即上一行转移到下一行。
同一行内的位置可以互相转移，所以可以对每一行内进行高斯消元，那么复杂度是$O(n^4)$，但是发现高斯消元的矩阵中每行只有三个位置有数，这个矩阵叫三对角矩阵，观察这个矩阵，发现可以O(n)消元。复杂度$O(n^2)$
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int mod = , N = ;
const double f31 = 1.0 / 3.0, f32 = 2.0 / 3.0, f41 = 1.0 / 4.0, f43 = 3.0 / 4.0, f38 = 8.0 / 3.0, f23 = 3.0 / 2.0; double dp[N][N], a[N][N];
int n, m, x, y; int ksm(int a,int b) {
int res = ;
while (b) {
if (b & ) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= ;
}
return res;
} void Make(int i) {
a[][] = f32;
a[][] = -f31;
a[][m + ] = f31 * dp[i + ][] + ;
a[m][m - ] = -f31;
a[m][m] = f32;
a[m][m + ] = f31 * dp[i + ][m] + ;
for (int j = ; j < m; ++j) {
a[j][j - ] = -f41;
a[j][j + ] = -f41;
a[j][j] = f43;
a[j][m + ] = f41 * dp[i + ][j] + ;
}
}
void pr(int l,int r) {
for (int i = l; i <= r; ++i) {
for (int j = ; j <= m + ; ++j)
printf("% .2lf ", a[i][j]);
puts("");
}
puts("");
}
void solve(int i) {
a[][] = ; a[][] *= f23; a[][m + ] *= f23;
for (int j = ; j < m; ++j) {
a[j][j - ] = ;
a[j][j + ] /= (a[j][j] + f41 * a[j - ][j]);
a[j][m + ] += f41 * a[j - ][m + ];
a[j][m + ] /= (a[j][j] + f41 * a[j - ][j]);
a[j][j] = ;
}
a[m][m - ] = ;
a[m][m + ] += (f31 * a[m - ][m + ]);
a[m][m + ] /= (a[m][m] + f31 * a[m - ][m]);
a[m][m] = ; dp[i][m] = a[m][m + ];
for (int j = m - ; j >= ; --j)
dp[i][j] = a[j][m + ] - a[j][j + ] * dp[i][j + ];
}
int main() {
n = read(), m = read(), x = read(), y = read();
if (m == ) {
printf("%.10lf", 2.0 * (n - x)); return ;
}
for (int i = n - ; i >= x; --i) {
Make(i);
solve(i);
}
printf("%.10lf", dp[x][y]);
return ;
}