矩阵乘法+\(AC\)自动机
是道很不错的题了
首先是前六十分，就是一个\(AC\)自动机上的套路\(dp\)，设\(dp[i][j]\)表示匹配出的长度为\(i\)在自动机上位置为\(j\)的方案数，转移的话就枚举下一个单词选择哪个放到自动机上一波匹配就好了
后面\(40\)分强行变成了另外一道题，\(L\)变成了\(1e8\)，一看就是矩乘的复杂度了
但是单词的长度都非常小，于是转移\(dp[i][j]\)的时候只需要从\(dp[i-1][]\)和\(dp[i-2][]\)里转移，发现这非常像斐波那契的转移，于是提前在\(ac\)机上的每个位置都处理一下对应的转移之后矩乘就好了
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define re register
#define LL long long
#define maxn 205
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const LL mod=1e9+7;
char S[maxn];
int fail[maxn],flag[maxn],son[maxn][26];
char T[55][maxn],len[maxn];
int n,m,L,cnt;
inline void ins()
{scanf("%s",S+1);int len=strlen(S+1),now=0;for(re int i=1;i<=len;i++) {if(!son[now][S[i]-'a']) son[now][S[i]-'a']=++cnt;now=son[now][S[i]-'a'];}flag[now]=1;
}
inline void Build()
{std::queue<int> q;for(re int i=0;i<26;i++) if(son[0][i]) q.push(son[0][i]);while(!q.empty()){int k=q.front();q.pop();flag[k]|=flag[fail[k]];for(re int i=0;i<26;i++)if(son[k][i]) fail[son[k][i]]=son[fail[k]][i],q.push(son[k][i]);else son[k][i]=son[fail[k]][i];}
}
namespace solve1
{int dp[maxn][maxn];inline int query(int x,int y){int now=x;for(re int i=1;i<=len[y];i++){if(flag[now]) return -1;now=son[now][T[y][i]-'a'];}if(flag[now]) return -1;return now;}inline void work(){dp[0][0]=1;for(re int i=0;i<L;i++)for(re int j=0;j<=cnt;j++)for(re int k=1;k<=n;k++){if(i+len[k]>L) continue;if(!dp[i][j]) continue;int v=query(j,k);if(v==-1) continue;dp[i+len[k]][v]=(dp[i+len[k]][v]+dp[i][j])%mod;}int ans=0;for(re int i=0;i<=cnt;i++) ans=(ans+dp[L][i])%mod;printf("%d\n",ans);}
}
namespace solve2
{LL ans[maxn][maxn],a[maxn][maxn];int M;inline void did_a(){LL mid[maxn][maxn];for(re int i=0;i<=M;i++)for(re int j=0;j<=M;j++) mid[i][j]=a[i][j],a[i][j]=0;for(re int k=0;k<=M;k++)for(re int i=0;i<=M;i++)for(re int j=0;j<=M;j++){a[i][j]+=((mid[i][k]*mid[k][j])%mod);if(a[i][j]>mod) a[i][j]%=mod;}}inline void did_ans(){LL mid[maxn][maxn];for(re int i=0;i<=M;i++)for(re int j=0;j<=M;j++) mid[i][j]=ans[i][j],ans[i][j]=0;for(re int k=0;k<=M;k++)for(re int i=0;i<=M;i++)for(re int j=0;j<=M;j++){ans[i][j]+=((a[i][k]*mid[k][j])%mod);if(ans[i][j]>mod) ans[i][j]%=mod;}}inline void quick(int b){while(b) {if(b&1) did_ans();b>>=1;did_a();}}inline void work(){M=cnt+cnt+1;for(re int i=0;i<=cnt;i++){if(flag[i]) continue;for(re int j=1;j<=n;j++)if(len[j]==1){int v=son[i][T[j][1]-'a'];if(!flag[v]) a[v+cnt+1][i+cnt+1]++;}else if(len[j]==2){int v=son[i][T[j][1]-'a'];int vv=son[v][T[j][2]-'a'];if(flag[v]||flag[vv]) continue;a[vv+cnt+1][i]++;}}for(re int j=cnt+1;j<=M;j++) a[j-cnt-1][j]++;for(re int i=0;i<=M;i++) ans[i][i]=1;quick(L);LL Ans=0;for(re int i=cnt+1;i<=M;i++) Ans=(ans[i][cnt+1]+Ans)%mod;printf("%lld\n",Ans);}
}
int main()
{scanf("%d%d%d",&n,&m,&L);for(re int i=1;i<=n;i++) scanf("%s",T[i]+1),len[i]=strlen(T[i]+1);for(re int i=1;i<=m;i++) ins();Build();if(L<=100) solve1::work();else solve2::work();return 0;
}
