题解 P6125【[JSOI2009]有趣的游戏】

· · 题解

\text{Link}

题意

给你 n 个长为 l 的字符串 a_{1,2,...,n}，字符集大小为 m，每次随机在末尾添加一个字符，当当前字符串包含字符串 a_i 时结束操作，对 1\le i\le n 问 a_i 成为结束操作时所包含的字符串的概率。

1\le n,l,m\le10

思路

我们建出 \text{ACAM} 和其 \text{Fail} 树，然后问题就变成了 \text{Fail} 树上停于某一点的概率。

这让我们容易联想到高斯消元，但是我们并不会求经过 x 点的概率。

然后我们可以设 f_x 为经过 x 点的期望。则我们有 f_x=[x=0]+\sum_y\text{P}_{y\to x}f_y。

然后我们就可以对其进行高斯消元了。

时间复杂度 O(n^3l^3)。

当然有 O(n^3) 的高论生成函数做法，但我不会。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff

}
const int N=100+10;
#define Tr ACAM.a[cur].ch
#define pid pair<int,double>
#define mpr make_pair
int n,l,m,endp[N];
double A[N][N],ans[N],p[N],q[N];
char str[N];
vector<pid>e[N];
struct AC_AutoMaton{
    #define son a[cur].ch
    int fail[N];
    int cnt=0;
    struct node{
        int ch[10];
        bool endp;
    }a[N];
    inline void insert(char *s,int n,int x){
        int cur=0;
        for(int i=1;i<=n;i++){
            int x=s[i]-'A'; 
            if(!son[x]) son[x]=++cnt;
            cur=son[x];
        }
        endp[x]=cur;
        a[cur].endp=1;
    }
    inline void getfail(){
        queue<int>q;
        for(int i=0;i<m;i++){
            if(a[0].ch[i]) q.push(a[0].ch[i]);
        }
        while(!q.empty()){
            int cur=q.front();
            q.pop();
            for(int i=0;i<m;i++){
                if(!son[i]){
                    son[i]=a[fail[cur]].ch[i];
                }else{
                    int v=fail[cur];
                    fail[son[i]]=a[v].ch[i];
                    q.push(son[i]);
                }
            }
        }
    }
    inline void build(){
        for(int i=0;i<=cnt;i++){
            if(!a[i].endp){
                for(int j=0;j<m;j++){
                    e[a[i].ch[j]].push_back(mpr(i,p[j+1]/q[j+1]));
                }
            }
        }
        for(int i=0;i<=cnt;i++){
            A[i+1][i+1]=-1;
            if(i==0) A[i+1][cnt+2]=-1;
            for(int j=0;j<e[i].size();j++){
                int t=e[i][j].first;
                double w=e[i][j].second;
                A[i+1][t+1]+=w;
            }
        }
    }
}ACAM;
inline void Gauss(int n){
    for(int i=1;i<=n;i++){
        int k=i;
        for(int j=i+1;j<=n;j++){
            if(fabs(A[j][i])>fabs(A[k][i])){
                k=j;
            }
        }
        for(int j=1;j<=n+1;j++){
            swap(A[i][j],A[k][j]);
        }
        for(int j=1;j<=n;j++){
            if(i!=j){
                double res=A[j][i]/A[i][i];
                for(int l=i+1;l<=n+1;l++){
                    A[j][l]-=A[i][l]*res;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        ans[i]=A[i][n+1]/A[i][i];
    }
}
int main(){
    n=read(),l=read(),m=read();
    for(int i=1;i<=m;i++){
        p[i]=read(),q[i]=read();
        if(p[i]==0) p[i]=0.000001;
    }
    for(int i=1;i<=n;i++){
        readstr(str);
        ACAM.insert(str,l,i);
    }
    ACAM.getfail();
    ACAM.build();
    Gauss(ACAM.cnt+1);
    for(int i=1;i<=n;i++){
        printf("%.2lf\n",max(ans[endp[i]+1],0.0));
    }
}

再见 qwq~