【BZOJ1444】[Jsoi2009]有趣的游戏
Description
Input
注意 是0<=P
Output
Sample Input
Sample Output
HINT
30%的数据保证, n ≤ 2. 50%的数据保证, n ≤ 5. 100%的数据保证, n , l, m≤ 10.
题解：本题的做法真的很多啊，概率DP，期望DP，当然还有矩乘黑科技~
就是先跑AC自动机，弄出转移矩阵，然后自乘50次就行了。
#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
",ans[i]);
return 0;
}
/*
1 10 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
1 10
AAAAAAAAAA
*/