ant

在一个奇怪的 \(n*m\) 的平面上有一只蚂蚁，蚂蚁一开始在 \((0,0)\) 这个位置。

这个平面的奇怪之处在于，从 \((n-1,i)\) 这个点向右走，就会到达 \((0,i)\)，从 \((i,m-1)\) 向上走，就会到达 \((i,0)\)。

这只蚂蚁每一步会随机地向上或者向右走一格，直到它到达 \((x,y)\)，求蚂蚁走过的期望步数。

\(n,m\leq 100\)

首先,\(O(n^3)\)的算法是不难想到的，设立最左列最下行可以使用高斯消元可以容易地得到，但这样的代码是较为复杂的（对我而言），当然这不适用于香猪

但由于这道题输出为浮点数，所以这道题可以有诡异的做法，我们将在文章的后面考虑将诡异的做法变为正常的做法

我们考虑将平面的\(x\)轴变成无限大，此时的终点为每一个\((x+\alpha n,y)\)

考虑对每列进行分别转移:设\(f_{i,j}\)表示能走到第\(i\)列，第\(i\)列第\(j\)列是当前列第一个被走到的概率

我们需要先预处理出它连续向上走的步数模\(m\)为\(x\)的概率\(g(x)\)

不难得到\(g(x)=2^{-x}\sum_{i=0}^\infty2^{-im}=\frac{2^{m-x-1}}{2^m-1}\)

有了这个我们就可以很容易地转移\(f_{i,j}\)了

然而我们需要得到的是步数的期望，我们考虑在每一个\(f_{i,j}\)单独计算期望

这是容易计算的，在每一个格子的期望连续向上走步数为\(1\)，这是你应该在小学老师处得知的

所以每个格子向答案的贡献为\(f_{i,j}*2\)

当然，在每个\(f_{x+\alpha n}\)需要特殊转移

我们设定一个较大的数\(B\)表示我们只考虑\(i\leq B\)时的贡献

朴素的做法时间复杂度为\(O(Bn^2)\),\(n=100\)时误差约为\((1-\frac{1}{n})^{{B\over n}+\epsilon}\approx 30\%\)，我想通过不能

我们发现转移过程为循环卷积，所以可以使用BS，且除了最初\(x\)次，转移为\(n-1\)次幂，可以预处理下来计算，过程\(n-1\)次贡献不会变

这样时间复杂度为\(O(Bn)\),\(n=100\)时误差约为\((1-\frac{1}{n})^{{B\over n}+\epsilon}\approx 10^{-44}\)，完全正确!

甚至当我们设\(B=200000\)时误差为\(10^{-9}\),同样通过

#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define ll long long
double f[105],tw[105],p[205],tv[105];
int n,m,x,y;
int main(){
	fre("ant");
	n=read;m=read;x=read,y=read;
	if(n>m)swap(n,m),swap(x,y);
	f[0]=1;double ans=0,g=1,h=1;
	for(int i=0;i<m;++i)g*=2;
	--g;
	for(int i=m;i--;)tw[i]=h/g,h*=2; 
	double o=1;
	for(int i=1;i<=m;++i)o*=0.5;
	o=1/(1-o);--o;o*=m;
	double sum=1;
	tv[0]=1;
	for(int i=1;i<n;++i){
		for(int j=0;j<m;tv[j]=0,++j)
			for(int k=0;k<m;++k)
				p[j+k]+=tv[j]*tw[k];
		for(int j=0;j<2*m;++j)
			tv[j%m]+=p[j],p[j]=0;
	}
	
	for(int i=0;i<=x;++i){
		if(i%n==x){sum=0;
			for(int j=1;j<m;++j){
				int w=(j+y)%m;
				ans+=f[w];
				f[(w+1)%m]+=f[w]/=2;
				sum+=f[w];
			}f[y]=0;
		}else{ans+=sum*2;
			for(int j=0;j<m;++j){
				for(int k=0;k<m;++k)
					p[j+k]+=f[j]*tw[k];
				f[j]=0;
			}
			for(int j=0;j<2*m;++j)
				f[j%m]+=p[j],p[j]=0;
		}
	}
	for(int i=1;i<=2000;++i){
		ans+=sum*2*(n-1);
		for(int j=0;j<m;++j){
			for(int k=0;k<m;++k)
				p[j+k]+=f[j]*tv[k];
				f[j]=0;
		}
		for(int j=0;j<2*m;++j)
			f[j%m]+=p[j],p[j]=0;
		sum=0;
		for(int j=1;j<m;++j){
			int w=(j+y)%m;
			ans+=f[w];
			f[(w+1)%m]+=f[w]/=2;
			sum+=f[w];
		}f[y]=0;
	}double t=0;
	for(int i=0;i<m;++i)if(i!=y)t+=f[i];
	printf("%.11f\n",ans);
	return 0;
}

上述做法可以通过数学方法得到模意义下的答案，以后再填