Luogu P4052 [JSOI2007] Text generator Answer key

Topic link ：P4052 [JSOI2007] Text generator

The question ：

JSOI Give it to the team ZYX A task , Make a program called “ Text generator ” Computer software ： The users of the software are young people , What they're using now is GW Text generator v6 edition .

The software can generate some articles randomly —— Always generate a fixed length and completely random article . in other words , Every character in the generated article is completely random . If an article contains at least one word that users know , So we say this article is readable （ We call it articles $s$ Contains words $t$, If and only if the word $t$ It's the article $s$ The string of ）. however , Even by this standard , What users use now GW Text generator v6 The article generated by the version is also almost completely unreadable .ZYX Need to point out that GW Text generator v6 In all text generated , Number of readable text , In order to be able to succeed in v7 Updated version . Can you help him ？

The answer is right $10^4+7$ modulus .

For all test points , Guarantee ：

• $1\le n\le 60$,$1\le m\le 100$.
• $1\le |s_i|\le 100$, among $|s_i|$ Representation string $s_i$ The length of .
• $s_i$ It only contains capital English letters .

Obviously, it needs to be built $\mathtt{AC}$ automata . Contains words , More trouble .

Consider tolerance and exclusion , Calculate the number of words not included （ Number of unreadable text ）

「 Number of readable text 」 be equal to 「 Number of all texts 」 subtract 「 Number of unreadable text 」

「 Number of all texts 」 Obviously $26^m$

It's not hard to find out , An unreadable text in $\mathtt{AC}$ When running on the automaton , You won't encounter 「 Dangerous nodes 」 Of

「 Dangerous nodes 」 Include 「 Is the end of the string 」 Node and 「 Some or some suffixes are words 」 The node of

The handling of dangerous nodes is relatively simple , Just deal with it when building automata , See code for details

Then this topic is counting , consider dp

set up $f_{i,j}$ Said go $j$ Node No , The length of the text is $i$ When the number of programs

obviously $f_{0,0}=1$
$$f_{i+1,v}=\sum _{(u,v)\in E}{f}_{i,u}$$
there $(u,v)\in E$ It means that $\mathtt{AC}$ Automata exist $u$ Point to $v$ The edge of

「 Number of unreadable text 」 Is equal to ${\sum }_{0\le i\le \text{tot}}{f}_{m,i}$

Time complexity $O(26\times m\sum |s_i|)$

Complete code ：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(105)
#define L (int)(6e3+15)
const int p=1e4+7;
void add(int &a,int b){
    a=(a%p+b%p)%p;}
int qpow(int a,int b)
{
    
    int ans=1,base=a%p;
    while(b)
    {
    
        if(b&1) ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
struct Trie
{
    
    queue<int> q;
    int tot,trie[L][26],ed[L],fail[L],f[N][L];
    void insert(string s)
    {
    
        int u=0;
        for(int i=0; i<s.size(); i++)
        {
    
            int c=s[i]-'A';
            if(!trie[u][c])trie[u][c]=++tot;
            u=trie[u][c];
        }
        ed[u]=1;
    }
    void build()
    {
    
        for(int i=0; i<26; i++)
            if(trie[0][i])q.push(trie[0][i]);
        while(!q.empty())
        {
    
            int u=q.front(); q.pop();
            for(int i=0; i<26; i++)
            {
    
                if(trie[u][i])
                {
    
                    fail[trie[u][i]]=trie[fail[u]][i];
                    if(ed[fail[trie[u][i]]])ed[trie[u][i]]=1;
                    q.push(trie[u][i]);
                }else trie[u][i]=trie[fail[u]][i];
            }
        }
    }
    void solve(int m)
    {
    
        f[0][0]=1;
        for(int i=0; i<m; i++)
            for(int j=0; j<=tot; j++)
                for(int k=0; k<26; k++)
                    if(!ed[trie[j][k]])
                        add(f[i+1][trie[j][k]],f[i][j]);
        int res=qpow(26,m);
        for(int i=0; i<=tot; i++)
            res=((res-f[m][i])%p+p)%p;
        cout << res << '\n';
    }
}tr;

signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n,m; string s;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
    
        cin >> s;
        tr.insert(s);
    }
    tr.build(); tr.solve(m);
    return 0;
}

Reprint please explain the source