洛谷P3706 [SDOI2017]硬币游戏（概率生成函数+高斯消元）

题面

题解

不知道概率生成函数是什么的可以看看这篇文章，题解也在里面了

//minamoto

#include<bits/stdc++.h>

#define R register

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

using namespace std;

const int N=305,P=1e9+7;const double eps=1e-10;

double mp[N][N],b[N];char s[N];int bin[N],h[N][N],n,m;

inline int Hash(R int i,R int l,R int r){return ((h[i][r]-1ll*h[i][l-1]*bin[r-l+1])%P+P)%P;}

void Gauss(int n){

	fp(i,1,n){

		if(mp[i][i]>-eps&&mp[i][i]<eps){

			fp(j,i+1,n)if(mp[j][i]<-eps||mp[j][i]>eps){

				fp(k,i,n+1)swap(mp[i][k],mp[j][k]);

				break;

			}

		}

		double t=1.0/mp[i][i];fp(j,i,n+1)mp[i][j]*=t;

		fp(j,i+1,n){

			t=mp[j][i];

			fp(k,i,n+1)mp[j][k]-=mp[i][k]*t;

		}

	}

	fd(i,n-1,1)fp(j,i+1,n)mp[i][n+1]-=mp[j][n+1]*mp[i][j];

}

int main(){

//	freopen("testdata.in","r",stdin);

	scanf("%d%d",&n,&m);

	bin[0]=b[0]=1;

	fp(i,1,m)bin[i]=(bin[i-1]<<1)%P,b[i]=b[i-1]*2;

	fp(i,1,n){

		scanf("%s",s+1);

		fp(j,1,m)h[i][j]=((h[i][j-1]<<1)+(s[j]=='H'))%P;

	}

	fp(i,1,n){

		fp(j,1,n)fp(k,1,m)(Hash(i,1,k)==Hash(j,m-k+1,m))?mp[i][j]+=b[k]:0;

		mp[i][n+1]=-1;

	}

	fp(i,1,n)mp[n+1][i]=1;mp[n+1][n+2]=1;

	Gauss(n+1);

	fp(i,1,n)printf("%.8lf\n",mp[i][n+2]);

	return 0;

}

巴特西

洛谷P3706 [SDOI2017]硬币游戏（概率生成函数+高斯消元）

题面

题解

最新文章

热门文章