洛谷P4052 [JSOI2007]文本生成器题解

题目链接：P4052 [JSOI2007]文本生成器

题意：

JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。

该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 \(s\) 包含单词 \(t\)，当且仅当单词 \(t\) 是文章 \(s\) 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

答案对 \(10^4 + 7\) 取模。

对于全部的测试点，保证：

\(1 \leq n \leq 60\)，\(1 \leq m \leq 100\)。

\(1 \leq |s_i| \leq 100\)，其中 \(|s_i|\) 表示字符串 \(s_i\) 的长度。

\(s_i\) 中只含大写英文字母。

显然要建 \(\tt{AC}\) 自动机。包含单词，比较麻烦。

考虑容斥，计算不包含单词的数量（不可读文本数量）

「可读文本数量」等于「所有文本数量」减去「不可读文本数量」

「所有文本数量」显然是 \(26^m\)

不难发现，一个不可读文本在 \(\tt{AC}\) 自动机上跑的时候，是不会碰到「危险结点」的

「危险结点」包括「是字符串结尾」的结点和「某个或某些后缀是单词」的结点

危险结点的处理比较简单，只要在建自动机的时候处理一下就好了，具体看代码

然后这个题目是计数题，考虑dp

设 \(f_{i,j}\) 表示走到 \(j\) 号结点，文本长度为 \(i\) 时的方案数

显然 \(f_{0,0} = 1\) \[ f_{i+1,v} = \sum_{(u,v) \in E} f_{i,u} \] 这里的 \((u,v) \in E\) 表示在 \(\tt{AC}\) 自动机上存在 \(u\) 指向 \(v\) 的边

「不可读文本数量」就等于 \(\sum_{0 \le i \le \text{tot}} f_{m,i}\)

时间复杂度 \(O(26 \times m \sum |s_i|)\)

完整代码：

#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;
}