网格图随机游板子。

发现100ms以内有一车子，有无过了的大佬说说做法qwq

在网上看到了一篇博客讲的是类似于“带状矩阵”的高斯消元，个人实现是基于这种方法的。

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int r,a1,a2,a3,a4;
int id[105][105],tot;
long long p1,p2,p3,p4;
int fc[8005][8005];
inline long long ksm(long long a,int b){
	if(b==0){
		return 1;
	}
	if(b==1){
		return a;
	}
	long long tmp=ksm(a,b/2);
	if(b%2==0){
		return tmp*tmp%mod;
	} 
	else{
		return tmp*tmp%mod*a%mod;
	}
}
inline void init(){
	int a1,a2,a3,a4;
	cin>>r>>a1>>a2>>a3>>a4;
	long long inv=(a1+a2+a3+a4)%mod;
	long long invinv=ksm(inv,mod-2);
	p1=a1*invinv%mod;
	p2=a2*invinv%mod;
	p3=a3*invinv%mod;
	p4=a4*invinv%mod;
}
struct xzzxbbxccxbbxzz{
	int n;
	int *a[8005];
	void Init(int _n,int *x){
		n=_n;
		for(int i=0;i<=n;i++){
			a[i]=x;
			x+=8005;
		}
	}
	long long Guass(){
		long long tmp;
		int d=2*r;
		for(int i=1;i<=n;i++){
			long long inv=ksm(a[i][i],mod-2);
			for(int j=i+1;j<=i+d&&j<=n;j++){
				if(j!=i&&a[j][i]){
					tmp=a[j][i]*inv%mod;
					a[j][i]=0;
					for(int k=i+1;k<=i+d&&k<=n;k++){
						a[j][k]=(a[j][k]-(long long)tmp*a[i][k])%mod;
					}
					a[j][n+1]=(a[j][n+1]-(long long)tmp*a[i][n+1])%mod;
				}
			}	
		}
		int goal=id[52][52];
		for(int i=n;i>=goal;i--){
			long long inv=ksm(a[i][i],mod-2);
			int &t=a[i][n+1];
			t=inv*t%mod;
			for(int j=i-1;j>=goal;j--){
				a[j][n+1]=(a[j][n+1]-(long long)a[j][i]*t)%mod;
			}
		}
		return a[goal][n+1];
	}
}GE;
signed main(){
	init();
	for(int i=-r;i<=r;i++){
		for(int j=-r;j<=r;j++){
			if(i*i+j*j<=r*r){
				id[i+52][j+52]=++tot;
			}
		}
	}
	for(int x=-r;x<=r;x++){
		for(int y=-r;y<=r;y++){
			if(int f=id[x+52][y+52]){
				fc[f][f]=-1;
				if(int t=id[x-1+52][y+52]){
					fc[f][t]=p1;
				}
                if(int t=id[x+52][y-1+52]){
                	fc[f][t]=p2;
				}
                if(int t=id[x+1+52][y+52]){
                	fc[f][t]=p3;
				}
                if(int t=id[x+52][y+1+52]){
                	fc[f][t]=p4;
				}
                fc[f][tot+1]=-1;
			}
		}	
	}
	GE.Init(tot,&fc[0][0]);
	cout<<(GE.Guass()+mod)%mod<<endl;
}

上面是自己的勾石代码。400ms，自己算出来复杂度是 $r^3$ 的，问一下算的对不对qwq