洛谷 P-4045 密码

记AC的第一道黑题！

题意：已知一段密码包含了一些字符串，然后求满足条件的密码有多少个，数量小于42时还得全部输出

思路：

  1. 一开始WA了两个点，不知道WA的什么，索性把读入的字符串去重了，实际上不需要
  2. 建好AC自动机，同时记录当前点是哪个字符串的结尾，方便状态压缩
  3. 做一遍数位DP，如果所有状态(给的字符串)都能达到，则说明所构造出的密码有效
  4. 需要注意的是，加入一个字符后，整条fail边上的状态都能达到了，因为fail边上的点代表是当前点的后缀字符串（这就是WA的那两个点）
  5. 最后考虑小于42时的输出，显然再跑一边相同的dfs不就行了吗？把构造出来的密码放到set里面，完事

题目描述

众所周知，密码在信息领域起到了不可估量的作用。对于普通的登陆口令以，唯一的破解方法就是暴力破解——逐个尝试所有可能的字母组合，但这是一项很耗时又容易被发现的工作。所以，为了获取对方的登陆口令，在暴力破解密码之前，必须先做大量的准备工作。经过情报的搜集，现在得到了若干有用信息，形如：

       “我观察到，密码中含有字符串*。”

例如，对于一个10位的密码以及观察到的字符串hello与world,可能的密码组合为helloworld与worldhello;而对于6位的密码以及到的字符串good与day,可能的密码组合为gooday。

有了这些信息，就能够大大地减少尝试的次数了。请编一个程序，计算所有密码组合的可能。密码中仅可能包含a-z之间的小写字母。

输入格式

输入数据首先输入两个整数L,N，分别表示密码的长度与观察到子串的个数。

接下来N行，每行若干个字符，描述了每个观察到的字符串。

输出格式

输出数据第一行为一个整数，代表了满足所有观察条件字符串的总数。

若这个数字小于等于42，则按字典顺序输出所有密码的可能情况，每行一个，否则，只输出满足所有观察条件字符串的总数即可。

输入输出样例

输入
10 2
hello
world
输出
2
helloworld
worldhello

说明/提示

对于100%的数据，1<=L<=25,1<=N<=10,每个观察到的字符串长不超过10，并且保证输出结果小于2^63。

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 95+10;
const int mod = 1e9+7;
const double eps = 1e-7;

int L, N;
char s[15];
int trie[maxn][26], fail[maxn], ed[maxn], cnt;
ll dp[26][maxn][4200];

void insert(int id) {
    int len=strlen(s), p=0;
    for(int i=0; i<len; ++i) {
        int k=s[i]-'a';
        if(!trie[p][k]) trie[p][k]=++cnt;
        p=trie[p][k];
    }
    ed[p]=id;
}

void build() {
    queue<int> q;
    for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
    while(q.size()) {
        int now=q.front(); q.pop();
        for(int i=0; i<26; ++i) {
            if(trie[now][i]) {
                fail[trie[now][i]]=trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else trie[now][i]=trie[fail[now]][i];
        }
    }
}

ll dfs(int pos, int now, int state) {
    if(pos>L) {
        for(int i=1; i<=N; ++i) if(!(state>>i&1)) return 0;
        return 1;
    }
    if(~dp[pos][now][state]) return dp[pos][now][state];
    ll ans=0;
    for(int i=0; i<26; ++i) {
        int newstate=state;
        for(int j=trie[now][i]; j; j=fail[j]) newstate|=1<<ed[j];
        ans+=dfs(pos+1,trie[now][i],newstate);
    }
    return dp[pos][now][state]=ans;
}

priority_queue<string,vector<string>,greater<string> > possible;

void dfs1(int pos, int now, int state, string l) {
    if(pos>L) {
        for(int i=1; i<=N; ++i) if(!(state>>i&1)) return;
        possible.push(l);
        return;
    }
    if(!dp[pos][now][state]) return;
    for(int i=0; i<26; ++i) {
        int newstate=state;
        for(int j=trie[now][i]; j; j=fail[j]) newstate|=1<<ed[j];
        dfs1(pos+1,trie[now][i],newstate,l+char('a'+i));
    }
}

int main() {
    //ios::sync_with_stdio(false);
    L=read(), N=read();
    set<string> sset;
    string l;
    for(int i=1; i<=N; ++i) cin>>l, sset.insert(l);
    int tot=0;
    for(auto p: sset) {
        for(int i=0; i<p.size(); ++i) s[i]=p[i];
        s[p.size()]=0;
        insert(++tot);
    }
    N=tot;
    build();
    memset(dp,-1,sizeof(dp));
    ll ans=dfs(1,0,0);
    printf("%lld\n", ans);
    if(ans<=42) {
        dfs1(1,0,0,"");
        while(possible.size()) { cout<<possible.top()<<endl; possible.pop(); }
    }
}