BZOJ1030: [JSOI2007]文本生成器【AC自动机+DP】

1030: [JSOI2007]文本生成器

【题目描述】

传送门

【题解】

我们可以求出不包含任何单词的字符串数,然后总数减去就可以了。也就是我们要求在Trie树上不走到标记节点的方案树,如果这个节点的pre是被标记节点,那么这个节点也是,那么这题就是在AC自动机上做DP。
f[i][j]表示文章第i位,匹配到自动机上第j位的最优解;
转移方程:f[i][Son[j][k]]=f[i-1][j]
当然这个j节点不能被标记。

代码如下

#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=6005,MOD=10007;
int n,m,F[105][MAXN],Ans;char ch[MAXN];
void MO(int &x){if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
struct Acho{
    int Son[MAXN][30],pre[MAXN],cnt,que[MAXN],hd,tl;
    bool W[MAXN];
    void Insert(char *s){
        int Len=strlen(s),Now=0;
        for(int i=0;i<Len;i++){
            if(!Son[Now][s[i]-'A']) Son[Now][s[i]-'A']=++cnt;
            Now=Son[Now][s[i]-'A'];
        }
        W[Now]=1;
    }
    void Build(){
        hd=tl=0;
        for(int i=0;i<26;i++) if(Son[0][i]) que[++tl]=Son[0][i];
        while(hd^tl){
            int x=que[++hd];
            for(int i=0;i<26;i++)
            if(Son[x][i]){
                int f=pre[x];
                while(f&&!Son[f][i]) f=pre[f];
                pre[que[++tl]=Son[x][i]]=Son[f][i],W[Son[x][i]]|=W[Son[f][i]];
            }else Son[x][i]=Son[pre[x]][i];
        }
    }
    void DP(){
        F[0][0]=1;
        for(int k=1;k<=m;k++) for(int i=0;i<=cnt;i++) if(!W[i]&&F[k-1][i]) for(int j=0;j<26;j++)
        MO(F[k][Son[i][j]]+=F[k-1][i]);
    }
}Tre;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("prob.in","r",stdin);
    freopen("prob.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",ch),Tre.Insert(ch);
    Tre.Build();Tre.DP();Ans=1;
    for(int i=1;i<=m;i++) Ans=(Ans*26)%MOD;
    for(int i=0;i<=Tre.cnt;i++) if(!Tre.W[i]) MO(Ans-=F[m][i]);
    printf("%d\n",Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部