SDOI2017硬币游戏

枚举串，方便讨论

(n,m300)

很容易想到建出AC自动机后暴力高斯消元的(O(n^3m^3)40)分做法

SOL：

这题和CSTC2006歌唱王国很像

定义:
(a_{i,j,k})表示(A_i[1,k])是否等于(A_j[m-k+1,m])

(f_{i,j})表示(A_i)出现时长度为(j)的概率，其生成函数为(F_i(X))

(g_i)表示长度为(i)的序列未出现任何串的概率，其生成函数为(G(x))

[G(x)+sum F_i(x)=1+G(x)*x ]

对于任意一个串(i)

[G(x)*frac 1{2^m}x^m=sum_{j=1}^nsum_{k=1}^ma_{i,j,k}*F_j(x)*frac 1{2^{m-k}}x^{m-k} ]

将(x=1)代入二试：

[G(1)=sum^n_{j=1}sum^m_{k=1}a_{i,j,k}*F_j(1)*2^k ]

需解出(G(1),F_i(1))，加上(sum F_i(1)=1)，一共(n+1)个式子，高斯消元即可

时间复杂度(O(n^3))

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
#define ll long long
const int N=304,mod=1e9+7;
const double eps=1e-10;
int n,m,h[N][N],b[N];
char s[N];
double a[N][N],db[N];
inline int hsh(int x,int l,int r){
	return (h[x][r]-(ll)h[x][l-1]*b[r-l+1]%mod+mod)%mod;
}
inline void gauss(int n){
	for(int i=1,id;i<=n;i++){
		id=i;
		for(int j=i+1;j<=n;j++)
			if(fabs(a[j][i])>fabs(a[id][i]))id=i;
		if(id!=i)swap(a[id],a[i]);
		for(int j=i+1;j<=n;j++){
			double tmp=a[j][i]/a[i][i];
			for(int k=i;k<=n+1;k++){
				a[j][k]-=a[i][k]*tmp;
			}
		}
	}
	for(int i=n;i;i--){
		for(int j=i+1;j<=n;j++)
			a[i][n+1]-=a[i][j]*a[j][n+1];
		a[i][n+1]/=a[i][i];
	}
}
int main(){
	n=read();m=read();
	b[0]=db[0]=1;
	for(int i=1;i<=m;i++){
		b[i]=(b[i-1]<<1)%mod;
		db[i]=db[i-1]*2;
	}
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			h[i][j]=((h[i][j-1]<<1)+(s[j]=='H'))%mod;
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			for(int k=1;k<=m;k++)
				if(hsh(i,1,k)==hsh(j,m-k+1,m))a[i][j]+=db[k];
		a[i][n+1]=-1;
	}
	for(int i=1;i<=n;i++)
		a[n+1][i]=a[n+1][n+2]=1;
	gauss(n+1);
	for(int i=1;i<=n;i++)
		printf("%.8lf
",a[i][n+2]); 
	return (0-0);
}