洛谷 P4569 - [BJWC2011]禁忌(AC 自动机+矩阵乘法)
阅读原文时间:2023年07月08日阅读:2

题面传送门

又好久没做过 AC 自动机的题了,做道练练手罢(

首先考虑对于某个固定的字符串怎样求出它的伤害,我们考虑贪心,每碰到出现一个模式串就将其划分为一段,最终该字符串的代价就是划分的次数。具体来说我们记录一个 \(pre\) 表示上一次在 \(pre\) 与 \(pre-1\) 划分为一段,我们从前往后扫一遍,每扫到一个 \(i\),就检验 \(s[pre…i],s[pre+1…i],s[pre+2…i],\cdots,s[i…i]\) 中是否有子串在模式串中出现过,如果有就令答案加 \(1\),并将 \(pre\) 赋为 \(i\)。正确性显然。

显然这种多模式串的题可以想到 AC 自动机。建出自动机,然后设 \(dp_{i,j}\) 表示已经填好了前 \(i\) 个位置上的字符,当前匹配到了 \(j\) 号节点的概率,转移显然可以枚举 \(j\) 的子节点 \(k\),\(dp_{i+1,k}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\),那么怎么体现”划分完的部分就不考虑了“呢?很简单,如果 \(k\) 是匹配节点,那我们就令 \(dp_{i+1,\text{root}}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\) instead of \(dp_{i+1,k}\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\),并且由于期望的线性性,这边答案产生了 \(1\) 的贡献,故还需令 \(ans\leftarrow dp_{i,j}\times\dfrac{1}{\text{alpha}}\)。

由于这题 \(len\) 数据范围很大,故可以套路地想到矩阵快速幂。建立转移矩阵,快速幂转移即可。时间复杂度 \((\sum|s|)\log len\)。还有一个小问题,就是这个 \(ans\) 如何一边求 \(dp\) 的值一遍维护。我们考虑令矩阵的大小扩大 \(1\),即一般的矩阵快速幂我们是 \(\begin{bmatrix}dp_{i,1}\\dp_{i,2}\\\cdots\\dp_{i,m}\end{bmatrix}\) 转移到 \(\begin{bmatrix}dp_{i+1,1}\\dp_{i+1,2}\\\cdots\\dp_{i+1,m}\end{bmatrix}\),而这题我们考虑增加一行 \(ans\),即从 \(\begin{bmatrix}dp_{i,1}\\dp_{i,2}\\\cdots\\dp_{i,m}\\ans\end{bmatrix}\) 转移到 \(\begin{bmatrix}dp_{i+1,1}\\dp_{i+1,2}\\\cdots\\dp_{i+1,m}\\ans\end{bmatrix}\)。具体来说对于一个点 \(j\),如果它的儿子中有 \(c\) 个匹配点,那么我们就令 \(ans\leftarrow ans+dp_{i,j}\times\dfrac{c}{\text{alpha}}\),这个也可在转移矩阵中表示出来。

最后再多说一句,如果你矩阵乘法是使用矩阵乘向量,也就是矩阵在前,向量在后的写法,要将转移到的位置设作行号,从哪个位置转移设为列号,我因为这地方写反了调了好久……xtbz

typedef long double ld;
const int MAXL=75;
const int ALPHA=26;
int n,len,alpha;char buf[MAXL+5];
int ch[MAXL+5][ALPHA+2],fail[MAXL+5],ncnt=0;
bool ed[MAXL+5];
void insert(char *s){
    int len=strlen(s+1),cur=0;
    for(int i=1;i<=len;i++){
        if(!ch[cur][s[i]-'a']) ch[cur][s[i]-'a']=++ncnt;
        cur=ch[cur][s[i]-'a'];
    } ed[cur]=1;
}
void getfail(){
    queue<int> q;
    for(int i=0;i<alpha;i++) if(ch[0][i]) q.push(ch[0][i]);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=0;i<alpha;i++){
            if(ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);
            else ch[x][i]=ch[fail[x]][i];
        }
    }
}
struct mat{
    ld a[MAXL+5][MAXL+5];
    mat(){memset(a,0,sizeof(a));}
    mat operator *(const mat &rhs){
        mat res;
        for(int i=0;i<=ncnt;i++) for(int j=0;j<=ncnt;j++)
            for(int k=0;k<=ncnt;k++) res.a[i][j]+=a[i][k]*rhs.a[k][j];
        return res;
    }
};
int main(){
    scanf("%d%d%d",&n,&len,&alpha);
    for(int i=1;i<=n;i++) scanf("%s",buf+1),insert(buf);
    getfail();mat trs,mul,tt;
    for(int i=0;i<=ncnt;i++) for(int j=0;j<alpha;j++){
        if(ed[ch[i][j]]) trs.a[0][i]+=1.0/alpha,trs.a[ncnt+1][i]+=1.0/alpha;
        else trs.a[ch[i][j]][i]+=1.0/alpha;
    } ncnt++;trs.a[ncnt][ncnt]=1;
    for(int i=0;i<=ncnt;i++) mul.a[i][i]=1;
    for(;len;len>>=1,trs=trs*trs) if(len&1) mul=mul*trs;
    tt.a[0][0]=1;tt=mul*tt;printf("%.10Lf\n",tt.a[ncnt][0]);
    return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章