一、题目
蚂蚁一开始在 ((0,0)) 这个位置，平面大小为 (n imes m)，每次蚂蚁可以向右走或者是向上走，从 ((n-1,i)) 这个点向右走就会到达 ((0,i))，从 ((i,m-1)) 向上走就会到达 ((i,0))，问走到 ((x,y)) 的期望步数。
(n,mleq 100)
二、解法
为了便于下面的叙述，我们把蚂蚁的行走改成向下走和向左走，设 (dp[i][j]) 表示从 ((i,j)) 出发到达 ((0,0)) 的期望步数，显然转移有环，需要 (O(n^3m^3)) 的高斯消元。
关键问题在于减少未知数的数量，因为环只在边界出现，其它地方都是有顺序的，我们可以只设第一行和第一列为未知数（设主元），剩下每个点的期望步数都可以用主元加系数表示出来（直接递推即可），然后在主元的这些位置可以列出 (n+m-1) 个方程，足以解出 (n+m-1) 个未知数。
时间复杂度 (O((n+m)^3))
三、总结
主元法是处理转移环的套路，线性递推可以设少量主元直接递推，或者是设部分主元来减少未知数的数量。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define db double
#define eps 1e-12
const int M = 205;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k;db a[M][M];
struct node
{
db w[M];
node() {memset(w,0,sizeof w);}
node operator + (const node &b) const
{
node r;
for(int i=1;i<=k;i++)
r.w[i]=w[i]+b.w[i];
return r;
}
node operator / (const db &b) const
{
node r;
for(int i=1;i<=k;i++)
r.w[i]=w[i]/b;
return r;
}
void print()
{
for(int i=1;i<=k;i++)
printf("%.3f ",w[i]);
puts("");
}
}g[M][M];
db Abs(db x) {return x>0?x:-x;}
void gauss()
{
for(int i=1;i<k;i++)
{
for(int j=i;j<k;j++)
if(Abs(a[j][i])>eps)
{
swap(a[i],a[j]);
break;
}
for(int j=1;j<k;j++)
{
if(i==j || Abs(a[j][i])<=eps) continue;
db tmp=a[j][i]/a[i][i];
for(int l=i;l<=k;l++)
a[j][l]-=a[i][l]*tmp;
}
}
}
signed main()
{
n=read();m=read();k=n+m;
for(int i=1;i<=n;i++)
g[i][1].w[i]=1;
for(int i=2;i<=m;i++)
g[1][i].w[i+n-1]=1;
for(int i=2;i<=n;i++)
for(int j=2;j<=m;j++)
{
g[i][j]=g[i-1][j]/2+g[i][j-1]/2;
g[i][j].w[k]--;
}
a[1][1]=1;
for(int i=2;i<=n;i++)
{
node t=g[(i-2+n)%n+1][1]/2+g[i][m]/2;
t.w[k]--;
for(int j=1;j<=k;j++)
a[i][j]=t.w[j];
a[i][i]--;
}
for(int i=2;i<=m;i++)
{
node t=g[n][i]/2+g[1][(i-2+m)%m+1]/2;
t.w[k]--;int p=n+i-1;
for(int j=1;j<=k;j++)
a[p][j]=t.w[j];
a[p][p]--;
}
gauss();
db ans=0;int x=read()+1,y=read()+1;
for(int i=1;i<k;i++)
ans+=g[x][y].w[i]*a[i][k]/a[i][i];
ans-=g[x][y].w[k];
printf("%.9lf
",ans);
}