Circles of Waiting

求一个整点四连通随机游⾛，离原点距离超过R期望步数。R≤50。

题解

本质上就是网格图的随机游走。

\[ E_x=\sum_y P_{x,y}E_y+1 \]

相关联的变量较少，所以使用Band Matrix即可。时间复杂度 \(O(R^4)\)。

https://blog.csdn.net/lycheng1215/article/details/80180178

代码

貌似这题不写主元系数为0时的操作也是对的。

CO int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int p[4];
CO int N=103,O=51;
int idx[N][N],tot;
pair<int,int> pt[N*N];
CO int M=7845+5;
int a[M][M];

int main(){
    int R=read<int>();
    int all=0;
    for(int i=0;i<=3;++i) all+=read(p[i]);
    all=fpow(all,mod-2);
    for(int i=0;i<=3;++i) p[i]=mul(p[i],all);
    for(int y=-R;y<=R;++y)for(int x=-R;x<=R;++x)
        if(x*x+y*y<=R*R) idx[x+O][y+O]=++tot,pt[tot]=make_pair(x+O,y+O);
    for(int i=1;i<=tot;++i){
        a[i][i]=1,a[i][tot+1]=1;
        int x=pt[i].first,y=pt[i].second;
        for(int j=0;j<=3;++j)if(idx[x+dx[j]][y+dy[j]])
            a[i][idx[x+dx[j]][y+dy[j]]]=mod-p[j];
    }
    int lim=0;
    for(int i=1;i<=tot;++i){
        lim=max(lim,idx[pt[i].first][pt[i].second+1]);
        int inv=fpow(a[i][i],mod-2);
        for(int j=i+1;j<=lim;++j)if(a[j][i]){
            int coef=mul(mod-a[j][i],inv);
            for(int k=i;k<=lim;++k) a[j][k]=add(a[j][k],mul(coef,a[i][k]));
            a[j][tot+1]=add(a[j][tot+1],mul(coef,a[i][tot+1]));
        }
    }
    for(int i=tot;i>=1;--i){
        for(int j=i+1;j<=tot;++j)
            a[i][tot+1]=add(a[i][tot+1],mod-mul(a[i][j],a[j][tot+1])),a[i][j]=0;
        a[i][tot+1]=mul(a[i][tot+1],fpow(a[i][i],mod-2)),a[i][i]=1;
    }
    printf("%d\n",a[idx[O][O]][tot+1]);
    return 0;
}