天天看點

BZOJ 1030(AC自動機+dp)

傳送門

題面:

1030: [JSOI2007]文本生成器

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 6094  Solved: 2580

[Submit][Status][Discuss]

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

題面分析:

    首先,多串比對,我們不難想到用AC自動機去維護。

    不難發現,如果沒有限制,一個長度為m的字元串最多可能構成 26^m種字元串。而如果加上限制條件,我們直接去算可行的方案就相當困難。但是我們發現,不可行的方案相對來說比較好求,隻需要剔除完整的字元串的方案數即可。是以我們可以優先考慮西安求出不可行的方案數res,并用 26^m-res即為需要求的可行的結果。

    而對于不可行的方案數,我們可以用dp記錄方案數去求解。我們設dp[i][j]為目前長度為i的字元串處于Trie樹中的第j号結點所具有的方案數。

    根據AC自動機next數組的性質,我們不難發現,長度為i+1,位于第j個結點的方案數可以轉移到長度為i,位于第next[j][k]結點的方案數,即dp[i+1][j]=dp[i+1][j]+dp[i][next[j][k]]。而當我們周遊到第j 個結點時發現它可以作為終止結點,我們就跳過該結點,此時就可以求出不符合條件(湊不出完整字元串)的方案數了。

代碼:

#include <bits/stdc++.h>
#define maxn 105
using namespace std;
int dp[maxn][7000];
char s[500];
const int mod=10007;
int n,m;
struct Trie{
    int next[10000][26],fail[10000],End[10000],id,root;
    int newnode(){
        for(int i=0;i<26;i++){
            next[id][i]=-1;
        }
        End[id]=0;
        return id++;
    }
    void init(){
        id=0;
        root=newnode();
    }
    void Insert(char *str){
        int len=strlen(str);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][str[i]-'A']==-1){
                next[now][str[i]-'A']=newnode();
            }
            now=next[now][str[i]-'A'];
        }
        End[now]=1;
    }
    void build(){
        queue<int>que;
        fail[root]=root;
        for(int i=0;i<26;i++){
            if(next[root][i]==-1){
                next[root][i]=root;
            }
            else{
                fail[next[root][i]]=root;
                que.push(next[root][i]);
            }
        }
        while(!que.empty()){
            int now=que.front();
            que.pop();
            for(int i=0;i<26;i++){
                if(next[now][i]==-1){
                    next[now][i]=next[fail[now]][i];
                }
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    que.push(next[now][i]);
                }
            }
            End[now]|=End[fail[now]];//終點标志也需要轉移
        }
    }
}ac;
int powmod(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
void solve(){
    dp[0][0]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=ac.id;j++){
            if(ac.End[j]) continue;//如果目前位為某一個串的終點
            for(int k=0;k<26;k++){
                if(ac.End[ac.next[j][k]]) continue;
                dp[i][ac.next[j][k]]=(dp[i][ac.next[j][k]]+dp[i-1][j])%mod;
            }
        }
    }
    int res=0;
    for(int i=0;i<=ac.id;i++){
        res=(res+dp[m][i])%mod;
    }
    cout<<(powmod(26,m)-res+mod)%mod<<endl;
}
int main()
{
    scanf("%d%d",&n,&m);
    ac.init();
    while(n--){
        scanf("%s",s);
        ac.Insert(s);
    }
    ac.build();
    solve();
}