BZOJ2553:[BeiJing2011]禁忌 AC自动机+期望dp

思路:

首先考虑如果一个串固定时,如何求出最多的出现次数.

当模式串存在覆盖关系时,很显然可以舍弃掉一些.那么现在所有的串之间都不存在覆盖关系.

那么我们可以从前向后扫描,如果出现一个完整的模式串,答案加1,同时将指针移到下一个位置继续刚才的操作.

由于不存在覆盖关系,这样的贪心是很显然的,不信的话可以自己画图看看.

考虑将模式串建成AC自动机.令\(P[i][j]\)表示串长为\(i\),现在处于AC自动机上的节点\(j\)上的概率.这个很容易用矩阵乘法搞定.

那么我们的答案是是什么呢?

考虑从某个节点转移到某个完全包含某个模式串的节点,那么此时答案+1,同时状态回到根节点.我们只要在矩阵中加一维计数器来搞就行了.

其实没说什么= =  不懂自己看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int ch[80][26],fail[80],end[80],cnt,q[80],fr,ta;
 
char s[20],sav[6][20];int len[6];bool covered[6];
 
typedef long double f4;
 
struct Matrix{
    f4 d[81][81];int w,h;
    Matrix(){}
    Matrix(int _w,int _h):w(_w),h(_h){}
     
    void operator*=(const Matrix&B){
        register int i,j,k;
        Matrix res(w,B.h);
        for(i=0;i<res.w;++i)for(j=0;j<res.h;++j){
            res.d[i][j]=0;for(k=0;k<h;++k)res.d[i][j]+=d[i][k]*B.d[k][j];
        }
        *this=res;
    }
};
 
bool cover(int a,int b){
    if(len[a]<len[b])return 0;
    register int i,j;
    for(i=1;i+len[b]-1<=len[a];++i){
        bool ok=1;
        for(j=1;j<=len[b];++j)if(sav[a][i+j-1]!=sav[b][j])ok=0;
        if(ok)return 1;
    }
    return 0;
}
 
int main(){
    int n,L,k;scanf("%d%d%d",&n,&L,&k);register int i,j;
     
    for(i=1;i<=n;++i)scanf("%s",sav[i]+1),len[i]=strlen(sav[i]+1);
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(cover(i,j))covered[i]=1;
     
    bool allcovered=1;for(i=1;i<=n;++i)if(!covered[i])allcovered=0;
    if(allcovered)covered[1]=0;
     
    int p,y;
    for(i=1;i<=n;++i)if(!covered[i]){
        p=0;for(j=1;j<=len[i];++j){if(!ch[p][y=sav[i][j]-'a'])ch[p][y]=++cnt;p=ch[p][y];}
        end[p]=1;
    }
     
    for(j=0;j<k;++j)if(ch[0][j])q[ta++]=ch[0][j];
    int u,v,r;
    while(fr^ta){
        u=q[fr++];
        for(j=0;j<k;++j){
            if((v=ch[u][j])){
                q[ta++]=v;
                for(r=fail[u];r&&!ch[r][j];r=fail[r]);
                end[v]|=end[fail[v]=ch[r][j]];
            }else ch[u][j]=ch[fail[u]][j];
        }
    }
     
    Matrix res(1,cnt+2);res.d[0][0]=1;
     
    Matrix add(cnt+2,cnt+2);add.d[cnt+1][cnt+1]=1;
    for(i=0;i<=cnt;++i){
        for(j=0;j<k;++j){
            if(end[ch[i][j]])add.d[i][cnt+1]+=(f4)1/k,add.d[i][0]+=(f4)1/k;
            else add.d[i][ch[i][j]]+=(f4)1/k;
        }
    }
     
    for(;L;L>>=1,add*=add)if(L&1)res*=add;
     
    double output=res.d[0][cnt+1];
    printf("%.6lf",output);
     
     
    return 0;
}