【BZOJ1444】[Jsoi2009]有趣的游戏

#include <cstdio>#include <cstring>#include <iostream>#include <queue>using namespace std;int n,l,m,tot;double c[30],ans[20];queue<int> q;struct node{	int ch[30],fail,dan;}p[110];char str[20];struct M{	double v[110][110];	M (){memset(v,0,sizeof(v));}	double* operator [](int x)	{return v[x];}	M operator * (M a) const	{		M c;		for(int i=1;i<=tot;i++)	for(int j=1;j<=tot;j++)	for(int k=1;k<=tot;k++)	c[i][j]+=v[i][k]*a[k][j];		return c;	}};M x;void build(){	int i,u;	q.push(1);	while(!q.empty())	{		u=q.front(),q.pop();		for(i=0;i<m;i++)		{			if(!p[u].ch[i])			{				if(u==1)	p[u].ch[i]=1;				else	p[u].ch[i]=p[p[u].fail].ch[i];				continue;			}			q.push(p[u].ch[i]);			if(u==1)			{				p[p[u].ch[i]].fail=1;				continue;			}			p[p[u].ch[i]].fail=p[p[u].fail].ch[i];		}	}}int main(){	scanf("%d%d%d",&n,&l,&m);	int i,j,u;	double a,b;	for(i=0;i<m;i++)	scanf("%lf%lf",&a,&b),c[i]=a/b;	for(tot=i=1;i<=n;i++)	{		scanf("%s",str),u=1;		for(j=0;j<l;j++)		{			if(!p[u].ch[str[j]-‘A‘])	p[u].ch[str[j]-‘A‘]=++tot;			u=p[u].ch[str[j]-‘A‘];		}		p[u].dan=i;	}	build();	for(i=1;i<=tot;i++)	{		if(p[i].dan) x[i][i]=1;		else	for(j=0;j<m;j++)	x[i][p[i].ch[j]]+=c[j];	}	for(i=1;i<=50;i++)	x=x*x;	for(i=1;i<=tot;i++)	if(p[i].dan)	ans[p[i].dan]=x[1][i];	for(i=1;i<=n;i++)	printf("%.2lf\n",ans[i]);	return 0;}/*1 10 101 101 101 101 101 101 101 101 101 101 10AAAAAAAAAA */