1030: [JSOI2007]文本生成器
Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 6271 Solved: 2673
[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
A
B
Sample Output
HINT
题意：
给你$N$个单词，文章长度$M$，求长度为$M$且包含至少一个单词的文章个数。
文章中只能出现大写字母。
题解：
求串个数的问题一般都是按长度$dp$，那么这道题我们可以设$dp(i)$表示长度为$i$的合法文章个数。
但这题有很多个单词，我们无法像单个单词那样记录当前文章和每个单词末尾的匹配位数，会$MLE$。
此时我们需要转化问题。注意到$ans=26^M-{不合法文章数}$，问题就被转化成有多少一个单词都不包含的文章。
这就相当于在$AC$自动机上走$M$步，不能走$end$节点的方案数。
设$dp(i,j)$表示在$AC$自动机上走了$j$步，走到$i$这个点的方案数，按遍历顺序转移即可。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; #define MAXN 6005 #define MAXM 105 #define INF 0x7fffffff #define ll long long #define mod 10007 struct node{ ll son[30]; bool ise; }tree[MAXN]; ll tot=1,dp[MAXN][MAXM],nxt[MAXN]; bool inq[MAXN][MAXM]; char str[MAXN]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void add(char *str){ ll N=strlen(str),u=1; for(ll i=0;i<N;i++){ ll ch=str[i]-'A'; if(!tree[u].son[ch]) tree[u].son[ch]=++tot; u=tree[u].son[ch]; } tree[u].ise=1; return; } inline void get_nxt(){ for(ll i=0;i<26;i++) tree[0].son[i]=1; queue<ll> q; q.push(1); while(!q.empty()){ ll u=q.front();q.pop(); for(ll i=0;i<26;i++) if(!tree[u].son[i]) tree[u].son[i]=tree[nxt[u]].son[i]; else{ q.push(tree[u].son[i]); nxt[tree[u].son[i]]=tree[nxt[u]].son[i]; tree[tree[u].son[i]].ise|=tree[nxt[tree[u].son[i]]].ise; } } return; } inline void bfs(ll M){ queue<ll> q1,q2; q1.push(1); q2.push(0); dp[1][0]=1; while(!q1.empty() && !q2.empty()){ ll u=q1.front();q1.pop(); ll l=q2.front();q2.pop(); inq[u][l]=0; //cout<<u<<" "<<l<<" "<<dp[u][l]<<endl; for(ll i=0;i<26;i++) if(l+1<=M && !tree[tree[u].son[i]].ise){ dp[tree[u].son[i]][l+1]+=dp[u][l]%mod; dp[tree[u].son[i]][l+1]%=mod; if(!inq[tree[u].son[i]][l+1]){ q1.push(tree[u].son[i]),q2.push(l+1); inq[tree[u].son[i]][l+1]=1; } } } return; } inline ll power(ll a,ll b){ ll ans=1; while(b){ if(b&1) ans*=a%mod,ans%=mod; a*=a%mod;a%=mod;b>>=1; } return ans; } int main(){ //freopen("1.txt","w",stdout); ll N=read(),M=read(); for(ll i=1;i<=N;i++) scanf("%s",str),add(str); get_nxt(),bfs(M); ll ans=0; for(ll i=1;i<=tot;i++) ans+=dp[i][M]%mod,ans%=mod; printf("%lld ",(power(26,M)%mod-ans%mod+mod)%mod); return 0; }