【bzoj1444】【jsoi2009】【有趣的游戏】【AC自动机+矩阵乘法】

注意 是0<=P

 30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.

题解：

         对所有玩家的串建立AC自动机.

         对于非单词节点,我们按概率转移到其他点.

         对于单词节点我们向它自己连一条概率为1的边.

         这样既可以累加答案有保证了不会从单词节点向外转移.

         这样就算出了在AC自动机上的转移矩阵a.

         对于第i个串,它在AC自动机上结束的位置是pos[i]

         那第i个串的答案就是a[1][pos[i]]的值.

         将转移矩阵自乘上几十遍就可以保证精度.

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 200
using namespace std;
int a[N][30],cnt=1,x,y,n,l,m,q[N],fail[N],pos[N],id[N];
char ch[N];
double p[N];
int read(){int x(0);char ch=getchar();while (ch<'0'||ch>'9') ch=getchar();while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x;
}
struct use{double a[N][N];use(){memset(a,0,sizeof(a));}friend use operator*(use a,use b){use ans;for (int i=1;i<=cnt;i++)for (int j=1;j<=cnt;j++)for (int k=1;k<=cnt;k++)ans.a[i][j]+=a.a[i][k]*b.a[k][j];return ans;}
}c;
void insert(int x){int len=strlen(ch),now=1;for (int i=0;i<len;i++){int u=ch[i]-'A'+1;if (a[now][u]) now=a[now][u];else a[now][u]=++cnt,now=a[now][u];}pos[now]=1;id[x]=now;
}
void getfail(){int h(0),t(1);q[0]=1;fail[1]=0;while (h<t){int u=q[h++];for (int i=1;i<=m;i++){if (!a[u][i]) continue;int k=fail[u];while (!a[k][i]) k=fail[k];fail[a[u][i]]=a[k][i];if (pos[a[k][i]]) pos[a[u][i]]=1;q[t++]=a[u][i];}}
}
void getmatrix(){//cout<<a[1][2]<<endl;for (int i=1;i<=cnt;i++) if (pos[i]) c.a[i][i]=1;else{for (int j=1;j<=m;j++){int u=i;while (!a[u][j]) u=fail[u];u=a[u][j];c.a[i][u]+=p[j]; }}
}
int main(){//freopen("a.in","r",stdin);n=read();l=read();m=read();for (int i=1;i<=m;i++){x=read();y=read();p[i]=(double)x/(double)y; }for (int i=1;i<=26;i++) a[0][i]=1; for (int i=1;i<=n;i++){scanf("%s",ch);insert(i);  }getfail();getmatrix();/*for (int i=1;i<=cnt;i++){for (int j=1;j<=cnt;j++)cout<<c.a[i][j]<<' ';cout<<endl;}*/for (int i=1;i<=50;i++) c=c*c;for (int i=1;i<=n;i++) printf("%.2lf\n",c.a[1][id[i]]);
}