BZOJ1444:[JSOI2009]有趣的游戏(AC自动机,矩阵乘法)

Description

Input

注意是0<=P, n , l, m≤ 10.

Output

Sample Input

input 1
3 2 2
1 2
1 2
AB
BA
AA

input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA

Sample Output

output 1
0.25
0.50
0.25

output 2
0.31
0.33
0.37

HINT

Solution

一个很显然的想法就是我们模拟然后往死里跑，跑到天荒地老，总会跑到精度符合要求的时候┑(￣Д ￣)┍

写个矩乘优化一下多跑几遍就可以过了。

具体建立矩阵就是设$m[x][y]$表示$x$点转移到$y$点的概率。

如果$x$点是结束点，$m[x][y]=1$。否则就$m[x][son[x][i]]+=p[i]$，其中$i$是枚举的字母。

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<queue>
 5 #define N (208)
 6 using namespace std;
 7 
 8 int n,m,l,tar[N];
 9 int sz,Son[N][12],Fail[N],End[N];
10 double x,y,p[N];
11 char s[N];
12 queue<int>q;
13 
14 struct Matrix
15 {
16     double m[N][N];
17     Matrix(){memset(m,0,sizeof(m));}
18 
19     Matrix operator * (const Matrix &b) const
20     {
21         Matrix c;
22         for (int i=0; i<=sz; ++i)
23             for (int j=0; j<=sz; ++j)
24                 for (int k=0; k<=sz; ++k)
25                     c.m[i][j]+=m[i][k]*b.m[k][j];
26         return c;
27     }
28 }A;
29 
30 void Insert(char s[],int id)
31 {
32     int now=0;
33     for (int i=0; i<l; ++i)
34     {
35         int c=s[i]-'A';
36         if (!Son[now][c]) Son[now][c]=++sz;
37         now=Son[now][c];
38     }
39     End[now]++; tar[id]=now;
40 }
41 
42 void Build_Fail()
43 {
44     for (int i=0; i<m; ++i)
45         if (Son[0][i]) q.push(Son[0][i]);
46     while (!q.empty())
47     {
48         int now=q.front(); q.pop();
49         for (int i=0; i<m; ++i)
50         {
51             if (!Son[now][i])
52             {
53                 Son[now][i]=Son[Fail[now]][i];
54                 continue;
55             }
56             Fail[Son[now][i]]=Son[Fail[now]][i];
57             q.push(Son[now][i]);
58         }
59     }
60 }
61 
62 void Solve()
63 {
64     for (int i=0; i<=sz; ++i)
65     {
66         if (End[i]) A.m[i][i]=1;
67         else for (int j=0; j<m; ++j) A.m[i][Son[i][j]]+=p[j];
68     }
69     for (int i=1; i<=50; ++i) A=A*A;
70     for (int i=1; i<=n; ++i)
71         printf("%.2lf
",A.m[0][tar[i]]);
72 }
73 
74 int main()
75 {
76     scanf("%d%d%d",&n,&l,&m);
77     for (int i=0; i<m; ++i)
78         scanf("%lf%lf",&x,&y), p[i]=x/y;
79     for (int i=1; i<=n; ++i)
80         scanf("%s",s), Insert(s,i);
81     Build_Fail(); Solve();
82 }