矩阵乘法+(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
",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
",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;
}