AC自动机+dp+矩阵乘法
常规思路是按基本串建立AC自动机
然鹅这题是按禁忌串建立AC自动机
对后缀是禁忌的点以及它的失配点做上标记$(a[i].ed)$，到时候不访问。
基本串转化为自动机上的边：设$p[j][i]$表示第$j$个节点加上第$i$个串会到的节点编号
在建好AC自动机后可以直接处理。
现在分类讨论（对，两份代码）
1.$L<=100,60pts$
直接在AC自动机上跑dp
设$f[j][i]$表示到点$j$长度为$i$的方案数
枚举基本串$1~k$，显然$f[p[j][k]][i+size[k]]+=f[j][i]$
$sz$表示AC自动机的节点数，则$ans=\sum_{i=0}^{sz}f[i][L]*[a[i].ed==0]$
2.基本词汇长度不超过$2,40pts$
开个$maxn*2$的矩阵，矩阵乘法瞎搞。
$f[i][L]=\sum_{j}f[j][l-1],j->i$
对于长度为2的情况，就开2倍的数组，用$i*2+1$暂时保存。
注意下标从0开始
（为啥我的常数这么大呢......）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 105
const int mod=1e9+;
int ans,sz,n,m,L,siz[N],f[N][N],p[N][N];
char q[N],s[N][N];
queue <int> h; struct node{int nxt[],f,ed;}a[];
void add(){
scanf("%s",q);
int len=strlen(q),u=;
for(int i=;i<len;++i){
if(!a[u].nxt[q[i]-'a'])
a[u].nxt[q[i]-'a']=++sz;
u=a[u].nxt[q[i]-'a'];
}a[u].ed=;
}
void acbuild(){
for(int i=;i<;++i) if(a[].nxt[i]) h.push(a[].nxt[i]);
while(!h.empty()){
int x=h.front();h.pop();
for(int i=;i<;++i){
int &to=a[x].nxt[i];
if(to){
a[to].f=a[a[x].f].nxt[i];
a[to].ed|=a[a[to].f].ed;
h.push(to);
}else to=a[a[x].f].nxt[i];
}
}
} struct mat{
int A[][];
mat(){memset(A,,sizeof(A));}
mat operator * (mat &tmp) const{
mat c;int w=sz<<|;
for(int i=;i<=w;++i)
for(int j=;j<=w;++j)
for(int k=;k<=w;++k)
c.A[i][j]=(c.A[i][j]+1ll*A[i][k]*tmp.A[k][j]%mod)%mod;
return c;
}
};
mat Pow(mat x,int y){
mat rs;
for(int i=;i<=sz;++i)
rs.A[i<<][i<<]=;
for(;y;y>>=,x=x*x)
if(y&) rs=rs*x;
return rs;
} void task1(){
f[][]=;
for(int i=;i<L;++i)
for(int j=;j<=sz;++j)
if(f[j][i])
for(int k=;k<=n;++k)
if(p[j][k]!=-&&i+siz[k]<=L)
f[p[j][k]][i+siz[k]]=(f[p[j][k]][i+siz[k]]+f[j][i])%mod;
for(int i=;i<=sz;++i) if(!a[i].ed) ans=(ans+f[i][L])%mod;
}
void task2(){
mat res;
for(int i=;i<=sz;++i){
for(int j=;j<=n;++j)
if(p[i][j]!=-){
if(siz[j]==) ++res.A[p[i][j]<<][i<<];
else ++res.A[p[i][j]<<][i<<|];
}
res.A[i<<|][i<<]=;
}res=Pow(res,L);
for(int i=;i<=sz;++i) if(!a[i].ed) ans=(ans+res.A[i<<][])%mod;
}
int main(){
memset(p,-,sizeof(p));
scanf("%d%d%d",&n,&m,&L);
for(int i=;i<=n;++i) scanf("%s",s[i]),siz[i]=strlen(s[i]);
for(int i=;i<=m;++i) add();
acbuild();
for(int i=;i<=n;++i)
for(int j=,u=;j<=sz;u=++j){
for(int k=;k<siz[i]&&!a[u].ed;++k)
u=a[u].nxt[s[i][k]-'a'];
if(!a[u].ed) p[j][i]=u;
}
if(L<=) task1();
else task2();
printf("%d",ans);
return ;
}