暑假 D6 T2 dict(AC自动机+DP)([JSOI2007]文本生成器)

题目描述

给定一个包含n个单词的字典，问有多少个长为m的串，满足至少包含字典中的一个单词，答案对10007取模，注意所有的串仅含大写字母且长度不超过100

输入格式

第一行两个整数m，n

接下来n行，每行给出字典中的一个单词

输出格式

输出一行一个整数，表示答案

样例输入

2 2

样例输出

100

数据范围

对于100%的数据，n≤60,m≤100

题解

正难则反

考虑求不经过跑到单词结尾的方案

f[i][j]:当前在i节点，走了j步

当i节点的儿子节点k没有end标记时，就可以向他转移

全排列26^m，最后减去f[i][m]（0≤i≤num）就是答案

转移时不需判断是否在树上有这个边，只要没有end就转移。因为在补全Trie树时，没有这个节点就会往上面连边

最后统计答案从0开始，一些完全不走Trie树边的答案记录在里面。

#include<bits/stdc++.h>
using namespace std;

const int mod=10007;
int n,m,num;
int go[6005][26],fail[6005];
int f[6005][105];//当前在i节点，不经过串结尾的方案 
bool end[6005];
char s[105];

int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void add(int len){
    int now=0;
    for(int i=0;i<len;i++){
        int c=s[i]-'A';
        if(!go[now][c]) go[now][c]=++num;
        now=go[now][c]; 
    }
    end[now]=true;
}

int q[6005],h,t;
void get_fail(){
    h=t=0;
    for(int i=0;i<26;i++) if(go[0][i]) q[t++]=go[0][i];
    while(h<t){
        int now=q[h++];
        for(int i=0;i<26;i++){
            if(!go[now][i]) go[now][i]=go[fail[now]][i];
            else {
                fail[go[now][i]]=go[fail[now]][i];
                end[go[now][i]]|=end[fail[go[now][i]]];
                q[t++]=go[now][i];
            }
        }
    }
}

int main(){
    freopen("dict.in","r",stdin);
    freopen("dict.out","w",stdout);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        add(strlen(s));
    }
    get_fail();
    f[0][0]=1;
    for(int i=1;i<=m;i++)
     for(int j=0;j<=num;j++)
      for(int k=0;k<26;k++)
       if(!end[go[j][k]])
        f[go[j][k]][i]=(f[go[j][k]][i]+f[j][i-1])%mod;
    int ans=qpow(26,m);
    for(int i=0;i<=num;i++)
     ans-=f[i][m];
    printf("%d",(ans%mod+mod)%mod);
}

View Code

f[i][j][0/1]也可以，最后求f[i][m]的和