BZOJ1030 JSOI2007 文本生成器

Description

　　JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？

Input

　　输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (<= 60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A..Z

Output

　　一个整数，表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

2 2

A

B

Sample Output

100

我们发现直接算包含的种类个数比较困难，所以考虑容斥：用总数量26m" role="presentation">26m26m减去不出现字串的个数。

我们发现不出现的充要条件是在AC自动机上从1开始行走m步不经过叶子节点。。。然后就在AC自动机上DP吧。。。

然后考虑对于一个节点u的第tmp个儿子，如果对于u从fail跳到0号节点的路径上有一个儿子v是叶子节点就不成立，check一下就好了

#include<bits/stdc++.h>

using namespace std;

#define N 6010

#define M 110

#define Mod 10007

struct Node{

    int id,fail,ch[26];

    void clean(){

        id=fail=0;

        memset(ch,0,sizeof(ch));

    }

}t[N];

int tot,n,m;

char s[M];

int dp[N][M];

void init(){

    tot=1;

    t[0].clean();t[1].clean();

    for(int i=0;i<26;i++)t[0].ch[i]=1;

}

int index(char c){return c-'A';}

void insert(char *s){

    int len=strlen(s);

    int u=1;

    for(int i=0;i<len;i++){

        int tmp=index(s[i]);

        if(!t[u].ch[tmp]){

            t[u].ch[tmp]=++tot;

            t[tot].clean();

        }

        u=t[u].ch[tmp];

    }

    t[u].id=1;

}

//建立fail指针

void buildFail(){

    queue<int> q;

    q.push(1);

    while(!q.empty()){

        int u=q.front();q.pop();

        for(int i=0;i<26;i++){

            int v=t[u].fail,w=t[u].ch[i];

            if(!w)continue;

            while(!t[v].ch[i])v=t[v].fail;

            t[w].fail=t[v].ch[i];

            q.push(w);

        }

    }

}

int fast_pow(int a,int b){

    int ans=1;

    while(b){

        if(b&1)ans=ans*a%Mod;

        b>>=1;

        a=a*a%Mod;

    }

    return ans;

}

//检查对于u的第tmp个儿子可不可行

bool check(int u,int tmp){

    int v=t[u].ch[tmp];

    while(u){

        if(t[v].id)return 0;

        u=t[u].fail;

        v=t[u].ch[tmp];

    }

    return 1;

}

void DP(){

    dp[1][0]=1;

    for(int k=1;k<=m;k++)

        for(int i=1;i<=tot;i++){

            if(t[i].id)continue;

            for(int j=0;j<26;j++){

                if(!check(i,j))continue;

                int u=i,v=t[i].ch[j];

                while(!v)u=t[u].fail,v=t[u].ch[j];

                dp[v][k]=(dp[v][k]+dp[i][k-1])%Mod;

            }

        }

}

int main(){

    init();

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){

        scanf("%s",s);

        insert(s);

    }

    buildFail();

    DP();

    int ans=fast_pow(26,m);

    for(int i=1;i<=tot;i++)ans=(ans-dp[i][m]+Mod)%Mod;

    printf("%d",(ans+Mod)%Mod);

    return 0;

}

巴特西

BZOJ1030 JSOI2007 文本生成器【AC自动机】【DP】*

BZOJ1030 JSOI2007 文本生成器

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

BZOJ1030 JSOI2007 文本生成器 【AC自动机】【DP】*

BZOJ1030 JSOI2007 文本生成器

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

BZOJ1030 JSOI2007 文本生成器【AC自动机】【DP】*