魔法咒语

Chandra 是一个魔法天才。从一岁时接受火之教会洗礼之后， Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。直到十四岁，开始学习威力强大的禁咒法术时， Chandra 才遇到了障碍。

根据火之魔法规则，禁咒的构成单位是

使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。例如，若 ”banana” 是唯一的忌讳词语， “an”、 ”ban”、 ”analysis” 是基本词汇，禁咒长度须是 11，则“bananalysis” 是无效法术， ”analysisban”、 ”anbanbanban”是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。谜题破解， Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。由于答案可能很大，你只需要输出答案模

Sol

把禁咒建AC自动机，预处理每一个基本词汇从每一个点开始跑会跑到哪，会不会碰到禁咒。

然后第一问暴力dp，第二问蒟乘

注意对于一个串，如果他的fail是禁咒，那么他也是非法点

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#define maxn 105
#define mod 1000000007
#define ll long long
using namespace std;
int n,N,m,l,tr[maxn][26],fail[maxn],p[maxn],tot,cnt,head[maxn];
int f[maxn][105];
string a[maxn];
char ch[maxn];
struct node{int v,nex,w;
}e[1000005];
void ins(){int len=strlen(ch),k=0;for(int i=0;i<len;i++){if(!tr[k][ch[i]-'a'])tr[k][ch[i]-'a']=++cnt;k=tr[k][ch[i]-'a'];}p[k]=1;
}
void build(){queue<int>q;for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);while(!q.empty()){int k=q.front();q.pop();for(int i=0;i<26;i++){if(tr[k][i]){fail[tr[k][i]]=tr[fail[k]][i];p[tr[k][i]]|=p[tr[fail[k]][i]]; q.push(tr[k][i]);}else tr[k][i]=tr[fail[k]][i];}}}
void add(int t1,int t2,int t3){e[++tot].v=t2;e[tot].w=t3;e[tot].nex=head[t1];head[t1]=tot;
}
struct no{ll v[505][505];
}s,A;
no operator *(no a,no b){no c;for(int i=0;i<=N;i++)for(int j=0;j<=N;j++){c.v[i][j]=0;for(int k=0;k<=N;k++){c.v[i][j]=(c.v[i][j]+1LL*a.v[i][k]*b.v[k][j]%mod)%mod;}}return c;
}
int main()
{cin>>n>>m>>l;for(int i=1;i<=n;i++){scanf("%s",ch);a[i]=(string)ch;}for(int i=1;i<=m;i++){scanf("%s",ch);ins();}build();for(int i=0;i<=cnt;i++){for(int j=1;j<=n;j++){int k=i,fl=0;if(p[k])continue;for(int x=0;x<a[j].size();x++){k=tr[k][a[j][x]-'a'];if(p[k]){fl=1;break;}}if(fl)continue;add(i,k,a[j].size());}}if(l<=100){f[0][0]=1;for(int x=0;x<=l;x++){for(int k=0;k<=cnt;k++){for(int i=head[k];i;i=e[i].nex){if(e[i].w+x>l)continue;f[e[i].v][x+e[i].w]=(f[e[i].v][x+e[i].w]+f[k][x])%mod;}}}int ans=0;for(int i=0;i<=cnt;i++)ans=(ans+f[i][l])%mod;cout<<ans<<endl;return 0;}N=cnt+cnt+1;for(int k=0;k<=cnt;k++){s.v[k+cnt+1][k]++;for(int i=head[k];i;i=e[i].nex){int j=e[i].v;if(e[i].w==1)s.v[k][j]++;else s.v[k][j+cnt+1]++;}}for(int i=0;i<=N;i++)A.v[i][i]=1;while(l){if(l&1)A=A*s;s=s*s;l>>=1;}ll ans=0;for(int i=0;i<=cnt;i++){ans=(ans+A.v[0][i])%mod;}cout<<ans<<endl;return 0;
}