正文
BZOJ1444[Jsoi2009]有趣的游戏——AC自动机+概率DP+矩阵乘法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目描述
输入
注意 是0<=P, n , l, m≤ 10.
输出
样例输入
input 1
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
样例输出
output 1
0.25
0.50
0.25
output 2
0.31
0.33
0.37
提示
一个显然的思路是在$AC$自动机上跑概率$DP$，答案就是当$T=∞$时，从根节点到每个终止节点的概率。那么我们可以建出$trie$图然后求出$trie$图的邻接矩阵，第$i$行第$j$列表示从$i$节点走到$j$节点的概率。因为到终止节点就会停止，所以终止节点到自己的概率为$1$。在保留两位小数的情况下只要对邻接矩阵进行$2^{50}$次矩乘即可得到在误差范围内的正确结果。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tr[200][20];
int fail[200];
int cnt;
double f[200][200];
char ch[20];
int n,l,m;
int end[200];
double P[20];
double g[200][200];
int p,q;
int pos[20];
void build(char *s,int num)
{
int now=0;
for(int i=0;i<l;i++)
{
int x=s[i]-'A';
if(!tr[now][x])
{
tr[now][x]=++cnt;
}
now=tr[now][x];
}
end[now]=1;
pos[num]=now;
}
void getfail()
{
queue<int>q;
for(int i=0;i<m;i++)
{
if(tr[0][i])
{
q.push(tr[0][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<m;i++)
{
if(tr[now][i])
{
fail[tr[now][i]]=tr[fail[now]][i];
q.push(tr[now][i]);
}
else
{
tr[now][i]=tr[fail[now]][i];
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&l,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&p,&q);
P[i]=(double)p/(double)q;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
build(ch,i);
}
getfail();
for(int i=0;i<=cnt;i++)
{
if(end[i])
{
f[i][i]=1;
continue;
}
for(int j=0;j<m;j++)
{
f[i][tr[i][j]]+=P[j];
}
}
for(int T=1;T<=50;T++)
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
for(int k=0;k<=cnt;k++)
{
g[i][j]+=f[i][k]*f[k][j];
}
}
}
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
f[i][j]=g[i][j];
g[i][j]=0.00;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%.2f\n",f[0][pos[i]]);
}
}
注意 是0<=P, n , l, m≤ 10.
输出
样例输入
input 1
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
样例输出
output 1
0.25
0.50
0.25
output 2
0.31
0.33
0.37
提示
一个显然的思路是在$AC$自动机上跑概率$DP$，答案就是当$T=∞$时，从根节点到每个终止节点的概率。那么我们可以建出$trie$图然后求出$trie$图的邻接矩阵，第$i$行第$j$列表示从$i$节点走到$j$节点的概率。因为到终止节点就会停止，所以终止节点到自己的概率为$1$。在保留两位小数的情况下只要对邻接矩阵进行$2^{50}$次矩乘即可得到在误差范围内的正确结果。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tr[200][20];
int fail[200];
int cnt;
double f[200][200];
char ch[20];
int n,l,m;
int end[200];
double P[20];
double g[200][200];
int p,q;
int pos[20];
void build(char *s,int num)
{
int now=0;
for(int i=0;i<l;i++)
{
int x=s[i]-'A';
if(!tr[now][x])
{
tr[now][x]=++cnt;
}
now=tr[now][x];
}
end[now]=1;
pos[num]=now;
}
void getfail()
{
queue<int>q;
for(int i=0;i<m;i++)
{
if(tr[0][i])
{
q.push(tr[0][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<m;i++)
{
if(tr[now][i])
{
fail[tr[now][i]]=tr[fail[now]][i];
q.push(tr[now][i]);
}
else
{
tr[now][i]=tr[fail[now]][i];
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&l,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&p,&q);
P[i]=(double)p/(double)q;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
build(ch,i);
}
getfail();
for(int i=0;i<=cnt;i++)
{
if(end[i])
{
f[i][i]=1;
continue;
}
for(int j=0;j<m;j++)
{
f[i][tr[i][j]]+=P[j];
}
}
for(int T=1;T<=50;T++)
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
for(int k=0;k<=cnt;k++)
{
g[i][j]+=f[i][k]*f[k][j];
}
}
}
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
f[i][j]=g[i][j];
g[i][j]=0.00;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%.2f\n",f[0][pos[i]]);
}
}
input 1
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
3 2 2
1 2
1 2
AB
BA
AA
input 2
3 4 2
1 2
1 2
AABA
ABAA
BAAA
样例输出
output 1
0.25
0.50
0.25
output 2
0.31
0.33
0.37
提示
一个显然的思路是在$AC$自动机上跑概率$DP$，答案就是当$T=∞$时，从根节点到每个终止节点的概率。那么我们可以建出$trie$图然后求出$trie$图的邻接矩阵，第$i$行第$j$列表示从$i$节点走到$j$节点的概率。因为到终止节点就会停止，所以终止节点到自己的概率为$1$。在保留两位小数的情况下只要对邻接矩阵进行$2^{50}$次矩乘即可得到在误差范围内的正确结果。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tr[200][20];
int fail[200];
int cnt;
double f[200][200];
char ch[20];
int n,l,m;
int end[200];
double P[20];
double g[200][200];
int p,q;
int pos[20];
void build(char *s,int num)
{
int now=0;
for(int i=0;i<l;i++)
{
int x=s[i]-'A';
if(!tr[now][x])
{
tr[now][x]=++cnt;
}
now=tr[now][x];
}
end[now]=1;
pos[num]=now;
}
void getfail()
{
queue<int>q;
for(int i=0;i<m;i++)
{
if(tr[0][i])
{
q.push(tr[0][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<m;i++)
{
if(tr[now][i])
{
fail[tr[now][i]]=tr[fail[now]][i];
q.push(tr[now][i]);
}
else
{
tr[now][i]=tr[fail[now]][i];
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&l,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&p,&q);
P[i]=(double)p/(double)q;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
build(ch,i);
}
getfail();
for(int i=0;i<=cnt;i++)
{
if(end[i])
{
f[i][i]=1;
continue;
}
for(int j=0;j<m;j++)
{
f[i][tr[i][j]]+=P[j];
}
}
for(int T=1;T<=50;T++)
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
for(int k=0;k<=cnt;k++)
{
g[i][j]+=f[i][k]*f[k][j];
}
}
}
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
f[i][j]=g[i][j];
g[i][j]=0.00;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%.2f\n",f[0][pos[i]]);
}
}
0.25
0.50
0.25
output 2
0.31
0.33
0.37
一个显然的思路是在$AC$自动机上跑概率$DP$，答案就是当$T=∞$时，从根节点到每个终止节点的概率。那么我们可以建出$trie$图然后求出$trie$图的邻接矩阵，第$i$行第$j$列表示从$i$节点走到$j$节点的概率。因为到终止节点就会停止，所以终止节点到自己的概率为$1$。在保留两位小数的情况下只要对邻接矩阵进行$2^{50}$次矩乘即可得到在误差范围内的正确结果。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int tr[200][20];
int fail[200];
int cnt;
double f[200][200];
char ch[20];
int n,l,m;
int end[200];
double P[20];
double g[200][200];
int p,q;
int pos[20];
void build(char *s,int num)
{
int now=0;
for(int i=0;i<l;i++)
{
int x=s[i]-'A';
if(!tr[now][x])
{
tr[now][x]=++cnt;
}
now=tr[now][x];
}
end[now]=1;
pos[num]=now;
}
void getfail()
{
queue<int>q;
for(int i=0;i<m;i++)
{
if(tr[0][i])
{
q.push(tr[0][i]);
}
}
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<m;i++)
{
if(tr[now][i])
{
fail[tr[now][i]]=tr[fail[now]][i];
q.push(tr[now][i]);
}
else
{
tr[now][i]=tr[fail[now]][i];
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&l,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&p,&q);
P[i]=(double)p/(double)q;
}
for(int i=1;i<=n;i++)
{
scanf("%s",ch);
build(ch,i);
}
getfail();
for(int i=0;i<=cnt;i++)
{
if(end[i])
{
f[i][i]=1;
continue;
}
for(int j=0;j<m;j++)
{
f[i][tr[i][j]]+=P[j];
}
}
for(int T=1;T<=50;T++)
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
for(int k=0;k<=cnt;k++)
{
g[i][j]+=f[i][k]*f[k][j];
}
}
}
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=cnt;j++)
{
f[i][j]=g[i][j];
g[i][j]=0.00;
}
}
}
for(int i=1;i<=n;i++)
{
printf("%.2f\n",f[0][pos[i]]);
}
}
