M_sea

洛谷4052 [JSOI2007]文本生成器
LuoguBZOJ分析比较套路了。总的单词个数是$26^m$,减去不可读的就是可读的。不可读的应该很容易求。建出A...
扫描右侧二维码阅读全文
12
2019/01

洛谷4052 [JSOI2007]文本生成器

Luogu

BZOJ

分析

比较套路了。

总的单词个数是$26^m$,减去不可读的就是可读的。

不可读的应该很容易求。建出AC自动机,然后在上面跑DP即可。

可以参照数数那题,不过没有上界限制还要更简单一点。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int L=100+10;
const int MOD=10007;

int n,m;
char s[L];

struct node {
    int son[26];
    int fail,last;
} t[6010];
int cnt=0;

inline void build(char* s,int len) {
    int now=0;
    for (re int i=0;i<len;++i) {
        if (!t[now].son[s[i]-'A'])
            t[now].son[s[i]-'A']=++cnt;
        now=t[now].son[s[i]-'A'];
    }
    t[now].last=1;
}

inline void getfail() {
    queue<int> Q;
    for (re int i=0;i<26;++i)
        if (t[0].son[i]) Q.push(t[0].son[i]);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        t[u].last|=t[t[u].fail].last;
        for (re int i=0;i<26;++i) {
            if (t[u].son[i]) {
                t[t[u].son[i]].fail=t[t[u].fail].son[i];
                Q.push(t[u].son[i]);
            }
            else t[u].son[i]=t[t[u].fail].son[i];
        }
    }
}

inline int FastPow(int a,int b) {
    int ans=1;
    for (;b;b>>=1,a=a*a%MOD)
        if (b&1) ans=ans*a%MOD;
    return ans;
}
inline void add(int& x,int y) { x+=y; if (x>=MOD) x-=MOD; }

int f[110][60010]; //f[i][j]表示前i个字符,在第j个节点的方案数

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        scanf("%s",s+1);
        build(s+1,strlen(s+1));
    }
    getfail();
    int ans=FastPow(26,m);
    f[0][0]=1;
    for (re int i=1;i<=m;++i)
        for (re int j=0;j<=cnt;++j)
            for (re int k=0;k<26;++k)
                if (!t[t[j].son[k]].last)
                    add(f[i][t[j].son[k]],f[i-1][j]);
    for (re int i=0;i<=cnt;++i) add(ans,MOD-f[m][i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 01 月 14 日 10 : 22 AM

发表评论