BZOJ 1444 JSOI2009 有趣的游戏 AC自动机+矩阵乘法

题目大意：给定n个长度为l的模式串，现在要用前m个大写字母生成一个随机串，每个字符有自己的出现几率，第一次出现的字符串获胜，求最终每个字符串的获胜几率

建出AC自动机，搞出转移矩阵

如果某个节点是模式串那么这个节点只向自己连一条概率为1的出边

然后把转移矩阵自乘50遍即可

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 120
using namespace std;
int n,l,m,limit;
int pos[M];
char s[M];
double possibility[M];
namespace Aho_Corasick_Automaton{
	struct Trie{
		Trie *son[10],*fail;
		int ed;
	}*root,mempool[M],*C=mempool;
	void Insert(Trie *&p,char *s,int pos)
	{
		if(!p) p=++C;
		if(!*s)
		{
			p->ed=pos;
			::pos[pos]=p-mempool;
			return;
		}
		Insert(p->son[*s-'A'],s+1,pos);
	}
	void Build_Tree()
	{
		static Trie *q[M];
		int i,r=0,h=0;
		for(i=0;i<m;i++)
			if(root->son[i])
				(q[++r]=root->son[i])->fail=root;
			else
				root->son[i]=root;
		while(r!=h)
		{
			Trie *p=q[++h];
			for(i=0;i<m;i++)
				if(p->son[i])
					(q[++r]=p->son[i])->fail=p->fail->son[i];
				else
					p->son[i]=p->fail->son[i];
		}
	}
}
class Matrix{
private:
	double xx[M][M];
public:
	Matrix()
	{
		memset(xx,0,sizeof xx);
	}
	Matrix(bool)
	{
		int i;
		memset(xx,0,sizeof xx);
		for(i=0;i<=limit;i++)
			xx[i][i]=1;
	}
	double* operator [] (int x)
	{
		return xx[x];
	}
	friend void operator *= (Matrix &x,Matrix y)
	{
		int i,j,k;
		Matrix z;
		for(i=1;i<=limit;i++)
			for(j=1;j<=limit;j++)
				for(k=1;k<=limit;k++)
					z[i][j]+=x[i][k]*y[k][j];
		x=z;
	}
}f;
int main()
{
	using namespace Aho_Corasick_Automaton;
	int i,x,p,q;
	cin>>n>>l>>m;
	for(i=0;i<m;i++)
	{
		scanf("%d%d",&p,&q);
		possibility[i]=(double)p/q;
	}
	for(i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		Insert(root,s+1,i);
	}
	Build_Tree();
	limit=C-mempool;
	for(i=1;i<=limit;i++)
	{
		if(mempool[i].ed)
			f[i][i]=1;
		else
			for(x=0;x<m;x++)
				f[i][mempool[i].son[x]-mempool]+=possibility[x];
	}
	for(i=1;i<=50;i++)
		f*=f;
	for(i=1;i<=n;i++)
		printf("%.2lf\n",f[1][pos[i]]);
	return 0;
}