BZOJ 1030: [JSOI2007]文本生成器 – [DP/AC自动机]


题目传送门(BZOJ)
>原文链接<

题解 :

正难则反, 我们换成求不可行方案数就好做了.

首先建立Trie图

状态 :

F[i][j]表示在Trie图上走了i步, 到了节点j的方案数

转移 :

F[i][j]F[i+1][son[j]]转移, 加法原理, 注意, 当且仅当json[j]都不是危险节点时, 才可以转移

答案 :

26^m减去所有非危险节点的状态的方案数就可以了

代码 :

#include 
#include 
#include 
#include 
using namespace std;
const int N = 21000;
const int mod = 10007;
int ch[N][27], fail[N], n, m, cnt=1;
char s[N];
bool flg[N];
int f[200][N];
queueq;
void Insert() {
    int p = 1;
    int len = strlen(s);
    for(int i = 0; i < len; i ++ ) {
        int &k = ch[p][s[i]-'A'+1];
        if(!k)k=++cnt;
        p = k;
    }
    flg[p] = 1;
}
void getFail() {
    int p;
    for(int i = 1; i <= 26; i ++ ) ch[0][i] = 1;
    q.push(1);
    while(!q.empty()) {
        p = q.front();q.pop();
        for(int i = 1; i <= 26; i ++ ) {
            if(ch[p][i]) fail[ch[p][i]] = ch[fail[p]][i], q.push(ch[p][i]);
            else ch[p][i] = ch[fail[p]][i];
        }
        flg[p] |= flg[fail[p]];
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++ ) {
        scanf("%s", s);
        Insert();
    }
    getFail();
    f[0][1] = 1;
    for(int i = 1; i <= m; i ++ ) for(int p = 1; p <= cnt; p ++ ) {
        if((!flg[p]) && f[i-1][p]) for(int k = 1; k <= 26; k ++ ) {
            (f[i][ch[p][k]] += f[i-1][p])%=mod;
        }
    }
    int ans = 1;
    for(int i = 1; i <= m; i ++ ) (ans *= 26) %= mod;
    for(int i = 1; i <= cnt; i ++ ) if(!flg[i]) {
         ((ans-=f[m][i]) += mod) %= mod;
    }
    printf("%d\n", ans);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注