摘要:AC自动机上高斯消元期望dp

luogu6125_[JSOI2009]有趣的游戏

题面

题目分析

首先把这个问题放在AC自动机上,从根节点开始随机遍历,遍历到一个结束点即结束.

我们设$f_i$为到达一个点的期望次数,则有以下方程:

也就是考虑一个点能从哪些点转移来,对这些点的期望次数乘上转移的概率求和即为这个点的期望.

这是一个dp序混乱的方程无法直接转移,但是注意到AC自动机上节点不超过$100$个,我们对每个点建立方程进行高斯消元即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "cstdio"
#include "iostream"
#include "cstring"
#include "cctype"
#include "algorithm"
#include "queue"
#define debug(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%lf\n",x)
#define debugc(x) printf("debug:%c\n",x)
#define endl putchar('\n')
#define R register
// #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const int big=110,small=11;
int n,m,l,NodeCnt;
int trie[small][big],end[big],endpos[big],fail[big];
double p[small],a[big][big];
char s[small];
inline int read()
{
char c(getchar());
int x(0);
for(;!isdigit(c);c=getchar());
for(;isdigit(c);x=(x*10)+(c^48),c=getchar());
return x;
}
inline void insert(int x)
{
int now(0),num;
for(R int i(0);i<l;++i)
{
num=s[i]-'A';
if(!trie[num][now])trie[num][now]=++NodeCnt;
now=trie[num][now];
}
endpos[x]=now,end[now]=true;
}
void GetFail()
{
std::queue<int>q;
for(R int i(0);i<m;++i)if(trie[i][0])q.push(trie[i][0]);
while(!q.empty())
{
int u=q.front();q.pop();
for(R int i(0);i<m;++i)
if(trie[i][u])fail[trie[i][u]]=trie[i][fail[u]],q.push(trie[i][u]);
else trie[i][u]=trie[i][fail[u]];
}
}
void get()
{
a[0][NodeCnt+1]=1;
for(R int i(0);i<=NodeCnt;++i)
{
a[i][i]=1.0;
// debugf(a[i][i]);
if(!end[i])for(R int j(0);j<m;++j)a[trie[j][i]][i]-=p[j];
}
}
inline void gauss(int n)
{
// for(R int i(0);i<=n;endl,++i)
// for(R int j(0);j<=n+1;++j)
// printf("%lf ",a[i][j]);
for(R int i(0);i<=n;++i)
{
// debug(n);
int max(i);
for(R int j(i+1);j<=n;++j)if(abs(a[max][i])<abs(a[j][i]))max=j;
for(R int j(0);j<=n+1;++j)std::swap(a[max][j],a[i][j]);
for(R int j(0);j<=n;++j)
{
if(j==i)continue;
double tmp=a[j][i]/a[i][i];
for(R int k(i+1);k<=n+1;++k)a[j][k]-=a[i][k]*tmp;
}
}
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
#endif
n=read(),l=read(),m=read();
for(R int i(0);i<m;++i)
{
int _p=read(),_q=read();
p[i]=(double)_p/(double)_q;
}
for(R int i(1);i<=n;++i)scanf("%s",s),insert(i);
GetFail(),get(),gauss(NodeCnt);
for(R int i(1);i<=n;++i)printf("%.2lf\n",a[endpos[i]][NodeCnt+1]/a[endpos[i]][endpos[i]]);
return 0;
}