[BJOI2017]魔法咒语

感觉解锁了矩乘新姿势。

传送门

首先裸dp显而易见对吧，$f[i][j]$为第i为时在AC自动机第j个位置的答案，但这样你要枚举l个位置，所以只能解决前60%的数据。

观察后40%数据，发现$f[i][j]​$只能由f[i-1]或f[i-2]的答案，让矩阵乘法有了可乘之机，数据范围也在引导着我们写矩乘。在我的印象里，矩乘只能由f[i-1]、f[i]转移到f[i]、f[i+1]，对二维的dp没有什么办法。

但由于我们可以预处理出AC自动机上每个位置能否放不同的单词及放置后结尾的位置，设第i处放第j个单词后结尾的位置为$a[i][j]​$。

所以可以这样矩乘(AC自动机只有2个节点的时候为例)：

	$f[i][1]$	$f[i][2]$	$f[i+1][1]$	$f[i+1][2]$
$f[i-1][1]$	0	0	$\sum_{i}^{n} (a[1][i]=1\&\&len[i]=2)$	左边意思是长度为2,且在第1个位置放置后合法且结尾在第1个位置的单词个数
$f[i-1][2]$	0	0	同	上
$f[i][1]$	1	0	右边意思是长度为1,且在第1个位置放置后合法且结尾在第2个位置的单词个数	$\sum_{i}^n(a[1][i]=2\&\&len[i]=1)$
$f[i][2]$	0	1	同	上

所以如果AC自动机中有$num$个元素，那么矩阵就是$2num\times 2num$的，把矩阵分为四块。

分别为：$(1,1)$到$(num,num)$（左上角），$(1,num+1)$到$(num,2num)$（右上角），$(num+1,1)$到$(2num,num)$（左下角），$(num+1,num+1)$到$(2num,2num)$（右下角）。

左上角全是0，因为$f[i]$已经求出，左下角是单位矩阵，因为$f[i]=f[i]$，右边预处理好填进去即可。

#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
#define mod 1000000007
using namespace std;
struct node{
    int cnt,ch[26],fail;
}t[1001];
struct Mat{
    ll d[201][201];
}h,e;
int num,tail,r[101],n;
int p,team[101],head,m;
ll f[101][101],ans;
char ch[101][101];
inline void insert(char *s){
    int u=1,l=strlen(s);
    for (int i=0; i<l; i++){
        int a=s[i]-'a';
        if (!t[u].ch[a]) t[u].ch[a]=++num;
        u=t[u].ch[a];
    }
    t[u].cnt=1;
}
inline void build(){
    head=tail=1; team[head]=1; t[1].fail=1;
    while (head<=tail){
        int x=team[head];
        // t[x].cnt|=t[t[x].fail].cnt;
        for (int i=0; i<26; i++){
            if (t[x].ch[i]){
                team[++tail]=t[x].ch[i];
                if (x==1){
                    t[t[x].ch[i]].fail=1;
                    continue;
                }
                t[t[x].ch[i]].fail=t[t[x].fail].ch[i];
                t[t[x].ch[i]].cnt|=t[t[t[x].fail].ch[i]].cnt;
            }
            else
                if (x==1) t[x].ch[i]=1;
                else t[x].ch[i]=t[t[x].fail].ch[i];
        }
        head++;
    }
}
inline int check(int x,int u){
    if (t[u].cnt) return -1;
    for (int i=0; i<r[x]; i++){
        int a=ch[x][i]-'a';	u=t[u].ch[a];
        if (t[u].cnt) return -1;
    }
    return u;
}
inline Mat mul(const Mat &a,const Mat &b){
    static Mat c;
    memset(c.d,0,sizeof(c.d));
    for (int k=1; k<=num*2; k++)
        for (int i=1; i<=num*2; i++){
            for (int j=1; j<=num*2; j++)
                c.d[i][j]=(c.d[i][j]%mod+a.d[i][k]*b.d[k][j]%mod)%mod;
    }
    return c;
}
inline Mat ksm(Mat a,ll b){
    Mat ret; memset(ret.d,0,sizeof(ret.d));
    for (int i=1; i<=num*2; i++) ret.d[i][i]=1;
    while (b){
        if (b&1) ret=mul(ret,a);
        a=mul(a,a); b>>=1;
    }
    return ret;
}
int main(){
    // freopen("0a.out","w",stdout);
    char s[101]; num=1;
    scanf("%d%d%d",&n,&m,&p);
    for (int i=1; i<=n; i++){
        scanf("%s",ch[i]);
        r[i]=strlen(ch[i]);
    }
    for (int i=1; i<=m; i++){
        scanf("%s",s);
        insert(s);
    }
    build();
if (p<=100){
    f[0][1]=1;
    for (int i=0; i<p; i++){
        for (int j=1; j<=num; j++){
            if (!f[i][j]) continue;
            for (int k=1; k<=n; k++){
                if (i+r[k]>p) continue;
                int v=check(k,j);
                if (v!=-1) f[i+r[k]][v]=(f[i+r[k]][v]+f[i][j])%mod;
            }
        }
    }
    for (int i=0; i<=num; i++) ans=(ans+f[p][i])%mod;
}
else{
    for (int i=1; i<=num; i++) h.d[i+num][i]=1;
    for (int i=1; i<=num; i++){
        for (int j=1; j<=n; j++){
            if (r[j]!=2) continue;
            int v=check(j,i);
            if (v!=-1) h.d[i][v+num]++;
        }
    }
    for (int i=1; i<=num; i++){
        for (int j=1; j<=n; j++){
            if (r[j]!=1) continue;
            // int v=i;
            // v=t[v].ch[ch[j][0]-'a'];
            // if (t[v].cnt) v=-1;
            int v=check(j,i);
            // printf("%d ",v);
            if (v!=-1) h.d[i+num][v+num]++;
        }
    }
    // for (int i=1; i<=num*2; i++){
    // 	for (int j=1; j<=num*2; j++)
    // 		printf("%lld ",h.d[i][j]);
    // 	puts("");
    // }
    h=ksm(h,p);
    Mat g; memset(g.d,0,sizeof(g.d));
    g.d[1][1+num]=1; g=mul(g,h);
    for(int i=1;i<=num;++i)
        ans=(ans+g.d[1][num+i])%mod;
    // for (int i=1; i<=num; i++) ans=(ans+h.d[num+1][i])%mod;
}
    printf("%lld\n",ans);
    return 0;
}