luogu P3706 [SDOI2017]硬币游戏

luogu

惯性思维想到建出AC自动机,然后高斯消元,再只考虑有用的项即可

考虑概率生成函数,设(F_i(x))为(x)获胜的概率生成函数,即第(j)项为序列长度为(j)时(i)获胜的概率,设(G(x))为到某个时刻还没人获胜的概率生成函数,可以列出两个柿子

(G(x)+sum_{i=1}^{n}F_i(x)=xG(x)+1)

(iin[1,n],(frac{x}{2})^mG(x)=sum_{j=1}^{m}sum_{k=1}^{n}[s_k[m-j+1,m]=s[1,j]](frac{x}{2})^{m-j}F_k(x))

第一个的意思是在一个未结束的序列后接个字符可能有人获胜可能每人获胜

第二个的意思是在一个没结束的序列后直接接上某个人的串，按道理他会获胜，但是可能接到一半就已经有人获胜了，假设往后接了(j)个字符后(k)获胜,那么这种情况出现代表(k)的串的长度为(j)的后缀和(i)的串的长度为(j)的前缀缀相同

我们要求的实际上是(F_i(1)),所以带入(x=1)后可得

(sum_{i=1}^{n}F_i(1)=1)

(iin[1,n],(frac{x}{2})^mG(1)=sum_{j=1}^{m}sum_{k=1}^{n}[s_k[m-j+1,m]=s[1,j]](frac{x}{2})^{m-j}F_k(1))

就有(n+1)个变量和(n+1)个方程了,高斯消元即可

#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double

using namespace std;
const int N=300+10;
const db eps=1e-8;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
db a[N][N],p2[N];
char cc[N];
uLL ha[N][N],pw[N],bs=233;
uLL gha(int o,int l,int r){return ha[o][r]-ha[o][l-1]*pw[r-l+1];}
int n,m;

int main()
{
	n=rd(),m=rd();
	pw[0]=1;
	for(int i=1;i<=m;++i) pw[i]=pw[i-1]*bs;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",cc+1);
		for(int j=1;j<=m;++j) ha[i][j]=ha[i][j-1]*bs+cc[j];
	}
	p2[0]=1;
	for(int i=1;i<=m;++i) p2[i]=p2[i-1]*0.5;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			for(int k=1;k<=n;++k)
				if(gha(k,m-j+1,m)==gha(i,1,j)) a[i][k]+=p2[m-j];
	for(int i=1;i<=n;++i)
		for(int k=1;k<=n;++k)
			a[i][k]-=a[i+1][k];//差分少掉一个变量&方程
	for(int k=0;k<=n;++k) a[n][k]=1;
	for(int i=1;i<=n;++i)
	{
		if(fabs(a[i][i])<eps)
		{
			for(int j=i+1;j<=n;++j)
				if(fabs(a[j][i])>eps)
				{
					for(int k=0;k<=n;++k) swap(a[i][k],a[j][k]);
					break;
				}
		}
		if(fabs(a[i][i])<eps) break;
		for(int j=1;j<=n;++j)
		{
			if(i==j) continue;
			db gg=a[j][i]/a[i][i];
			for(int k=0;k<=n;++k) a[j][k]-=a[i][k]*gg;
		}
	}
	for(int i=1;i<=n;++i) printf("%.8lf
",a[i][0]/a[i][i]);
	return 0;
}