[JSOI2009]密码

题目

复习\(\rm AC\)自动机来了

一道简单题，转化一些题意就是在\(\rm AC\)自动机走一条长度为\(L\)的路径，使得这条路径经过\(n\)个不同的目标点

求方案显然直接搞，设\(dp_{i,j,s}\)表示走了\(i\)步，目前在\(\rm AC\)自动机第\(j\)个节点，经过的节点的状态为\(s\)，转移显然随便转移

方案数不超过\(42\)的时候输出所有方案，显得非常睿智，感觉直接爆搜会\(T\)，于是提前处理一个数组\(f_{i,j,s}\)表示当前这个状态能否到达一个终点，利用这个数组剪枝复杂度就有保证了

代码

#include<bits/stdc++.h>
#define re register
#define LL long long
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=255;
LL dp[2][maxn][1025];
int s[maxn],fa[maxn],son[maxn][26];
char S[105];int n,m,L,len,o;
inline void ins(int x) {
    scanf("%s",S+1);int len=strlen(S+1);
    int now=0;
    for(re int i=1;i<=len;i++) {
        if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++m;
        now=son[now][S[i]-'a'];
    }
    s[now]|=(1<<(x-1));
}
namespace sub {
    bool f[26][maxn][1025],vis[26][maxn][1025];
    int b[26];
    bool find(int l,int x,int h) {
        if(l==L) {
            vis[l][x][h]=1;
            return f[l][x][h]=(h==len-1);
        }
        if(vis[l][x][h]) return f[l][x][h];
        vis[l][x][h]=1;
        for(re int i=0;i<26;i++) 
            f[l][x][h]|=find(l+1,son[x][i],h|s[son[x][i]]);
        return f[l][x][h]; 
    }
    inline void out() {
        for(re int i=1;i<=L;++i) putchar(b[i]+'a');
        puts("");
    }
    void Dfs(int l,int x,int h) {
        if(!f[l][x][h]) return;
        if(l==L) {
            if(h==len-1) out();
            return;
        }
        for(re int i=0;i<26;++i)
            b[l+1]=i,Dfs(l+1,son[x][i],h|s[son[x][i]]);
    }
    inline void solve() {
        find(0,0,0);Dfs(0,0,0);
    }
}
int main() {
    scanf("%d%d",&L,&n);
    for(re int i=1;i<=n;i++) ins(i);
    std::queue<int> q;
    for(re int i=0;i<26;++i) if(son[0][i]) q.push(son[0][i]);
    while(!q.empty()) {
        int k=q.front();q.pop();
        s[k]|=s[fa[k]];
        for(re int i=0;i<26;++i)
        if(son[k][i]) fa[son[k][i]]=son[fa[k]][i],q.push(son[k][i]);
        else son[k][i]=son[fa[k]][i];
    }
    dp[0][0][0]=1;len=(1<<n),o=0;
    for(re int i=0;i<L;i++,o^=1) {
        memset(dp[o^1],0,sizeof(dp[o^1]));
        for(re int j=0;j<=m;j++) 
            for(re int k=0;k<len;k++) {
                if(!dp[o][j][k]) continue;
                for(re int p=0;p<26;++p)
                    dp[o^1][son[j][p]][k|s[son[j][p]]]+=dp[o][j][k];
            }
    }
    LL ans=0;
    for(re int i=0;i<=m;i++) ans+=dp[o][i][len-1];
    printf("%lld\n",ans);
    if(ans<=42) sub::solve();
    return 0;
}

[JSOI2009]密码

原文：https://www.cnblogs.com/asuldb/p/11574800.html