BZOJ 2553 禁忌

首先我们要考虑给定一个串，如何将他划分，使得他有最多的禁忌串

我们只需要按里面出现的禁忌串们的出现的右端点排序然后贪心就可以啦

我们建出AC自动机，在AC自动机等价于走到一个包含禁忌串的节点就划分出一段

那么不妨设f(i,j)表示走了i步当前在AC自动机的j节点上

这样的DP方程跟BZOJ 1030是类似的

但是由于i可能会很大，但是j是很小的，又因为每一步的转移都是一样的

所以我们可以考虑矩阵乘法来优化DP

可是当我们用AC自动机构建了转移矩阵之后，我们会发现我们没办法算答案

我们只能算经过L步到达AC自动机某节点的概率

那么我们不妨新建节点表示答案，在每次出现禁忌串的时候在新建节点上贡献相应的期望

同时新建节点要将上次贡献得到的期望传递给下一次的转移

所以矩阵中n->n存在转移

值得一提的是：这个题目卡精度，我一开始写的double，结果WA了

去网上看了看题解之后默默的改成了long double，然后A了

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn=102;

int n,L,k,cnt;

bool vis[maxn];

char s[maxn];

int t[maxn][26];

int fail[maxn];

bool end[maxn];

struct Matrix{

    long double a[maxn][maxn];

    Matrix(){memset(a,0,sizeof(a));}

}A,ans;

queue<int>Q;

void insert(){

    scanf("%s",s+1);

    int len=strlen(s+1),now=1;

    for(int i=1;i<=len;++i){

        int id=s[i]-'a';

        if(!t[now][id])t[now][id]=++cnt;

        now=t[now][id];

    }end[now]=true;

}

void build_fail(){

    Q.push(1);fail[1]=0;

    while(!Q.empty()){

        int u=Q.front();Q.pop();

        end[u]|=end[fail[u]];

        for(int i=0;i<k;++i){

            int tmp=fail[u];

            while(tmp&&!t[tmp][i])tmp=fail[tmp];

            if(t[u][i]){

                fail[t[u][i]]=tmp?t[tmp][i]:1;

                Q.push(t[u][i]);

            }else t[u][i]=tmp?t[tmp][i]:1;

        }

    }A.a[n][n]=1;return;

}

void build_Matrix(){

    vis[1]=true;Q.push(1);

    long double tmp=1.0/k;

    while(!Q.empty()){

        int u=Q.front();Q.pop();

        for(int i=0;i<k;++i){

            if(!vis[t[u][i]]){

                vis[t[u][i]]=true;

                Q.push(t[u][i]);

            }

            if(end[t[u][i]]){

                A.a[u][n]+=tmp;

                A.a[u][1]+=tmp;

            }else A.a[u][t[u][i]]+=tmp;

        }

    }return;

}

Matrix operator *(const Matrix &A,const Matrix &B){

    Matrix C;

    for(int i=1;i<=n;++i){

        for(int j=1;j<=n;++j){

            for(int k=1;k<=n;++k){

                C.a[i][j]=C.a[i][j]+A.a[i][k]*B.a[k][j];

            }

        }

    }return C;

}

Matrix pow_mod(int p){

    Matrix tmp;

    for(int i=1;i<=n;++i)tmp.a[i][i]=1;

    while(p){

        if(p&1)tmp=tmp*A;

        A=A*A;p>>=1;

    }return tmp;

}

int main(){

    scanf("%d%d%d",&n,&L,&k);cnt=1;

    for(int i=1;i<=n;++i)insert();

    n=cnt+1;

    build_fail();build_Matrix();

    ans=pow_mod(L);

    printf("%.7lf\n",(double)(ans.a[1][n]));

    return 0;

}

巴特西

BZOJ 2553 禁忌

最新文章

热门文章