【BZOJ1444】[JSOI2009]有趣的游戏（高斯消元，AC自动机）

题面

BZOJ

题解

先把\(AC\)自动机构建出来，最好构成\(Trie\)图。然后这样子显然是在一个有向图中有一堆概率的转移，并且存在环，所以高斯消元解决。

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

struct Node{int son[26],fail,lst;}t[500];

int tot,n,m,l,pos[20];

char ch[50];

double g[200][200],p[50];

void insert(char *s,int id)

{

	int u=0;

	for(int i=1;i<=l;++i)

	{

		if(!t[u].son[s[i]-65])

			t[u].son[s[i]-65]=++tot;

		u=t[u].son[s[i]-65];

	}

	t[u].lst=id;pos[id]=u;

}

void Build()

{

	queue<int> Q;

	for(int i=0;i<m;++i)if(t[0].son[i])Q.push(t[0].son[i]);

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=0;i<m;++i)

			if(t[u].son[i])

				t[t[u].son[i]].fail=t[t[u].fail].son[i],Q.push(t[u].son[i]);

			else t[u].son[i]=t[t[u].fail].son[i];

		t[u].lst|=t[t[u].fail].lst;

	}

}

void Gauss()

{

	for(int i=0;i<=tot;++i)

	{

		int p=0;

		for(int j=i;j<=tot;++j)

			if(g[j][i]){p=j;break;}

		for(int j=0;j<=tot+1;++j)swap(g[i][j],g[p][j]);

		double t=g[i][i];

		for(int j=0;j<=tot+1;++j)g[i][j]/=t;

		for(int j=i+1;j<=tot;++j)

		{

			double d=g[j][i];

			for(int k=0;k<=tot+1;++k)

				g[j][k]-=g[i][k]*d;

		}

	}

	for(int i=tot;~i;--i)

	{

		g[i][tot+1]/=g[i][i];

		for(int j=i-1;j>=0;--j)

			g[j][tot+1]-=g[j][i]*g[i][tot+1];

		if(!g[i][tot+1])g[i][tot+1]=0;

	}

}

int main()

{

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

	for(int i=0;i<m;++i)

	{

		int a,b;

		scanf("%d%d",&a,&b);

		p[i]=1.0*a/b;

	}

	for(int i=1;i<=n;++i)

	{

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

		insert(ch,i);

	}

	Build();

	for(int i=0;i<=tot;++i)

		for(int j=0;j<m;++j)

			if(!t[i].lst)

				g[t[i].son[j]][i]+=p[j];

	for(int i=0;i<=tot;++i)g[i][i]-=1;

	for(int i=0;i<=tot;++i)if(t[i].lst)g[0][i]=1;else g[0][i]=0;g[0][tot+1]=1;

	Gauss();

	for(int i=1;i<=n;++i)printf("%.2lf\n",g[pos[i]][tot+1]);

	return 0;

}