LibreOJ 2180 「BJOI2017」魔法咒语

考虑前 60 分的做法：建出 ACAM，然后用 DP 模拟禁咒法术在 ACAM 上匹配的过程。

考虑后 40 分：发现转移的长度改变量不超过 2，考虑矩阵快速幂优化。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
const int M = 100;
const int mod = 1e9 + 7;
int n,m,l;
int len[N + 5];
char s[M + 5],t[M + 5];
int f[M + 5][M + 5];
namespace ACAM
{
    struct node
    {
        int ch[26];
        int fa,ed;
    } acam[M + 5];
    int las = 1,tot = 1;
    inline void insert(int x,int ed)
    {
        if(acam[las].ch[x])
        {
            acam[las = acam[las].ch[x]].ed |= ed;
            return ;
        }
        acam[las = acam[las].ch[x] = ++tot].ed |= ed;
    }
    int q[M + 5],head,tail;
    inline void get_fail()
    {
        q[++tail] = 1;
        for(register int i = 0;i < 26;++i)
            acam[0].ch[i] = 1;
        for(register int p;head < tail;)
        {
            p = q[++head];
            for(register int i = 0;i < 26;++i)
                if(acam[p].ch[i])
                    acam[acam[p].ch[i]].fa = acam[acam[p].fa].ch[i],q[++tail] = acam[p].ch[i],
                    acam[acam[p].ch[i]].ed |= acam[acam[acam[p].ch[i]].fa].ed;
                else
                    acam[p].ch[i] = acam[acam[p].fa].ch[i];
        }
    }
    inline int match(char *s,int len,int p)
    {
        if(acam[p].ed)
            return 0;
        for(register int i = 1;i <= len;++i)
        {
            p = acam[p].ch[s[i] - 'a'];
            if(acam[p].ed)
                return 0;
        }
        return p;
    }
}
struct Matrix
{
    int a[(M << 1) + 5][(M << 1) + 5];
    inline Matrix()
    {
        memset(a,0,sizeof a);
    }
    inline Matrix(int)
    {
        memset(a,0,sizeof a);
        for(register int i = 1;i <= (ACAM::tot << 1);++i)
            a[i][i] = 1;
    }
    inline int *operator[](const int &x)
    {
        return a[x];
    }
    inline const int *operator[](const int &x) const
    {
        return a[x];
    }
    inline Matrix operator*(const Matrix &o) const
    {
        Matrix ret;
        for(register int i = 1;i <= (ACAM::tot << 1);++i)
            for(register int j = 1;j <= (ACAM::tot << 1);++j)
                for(register int k = 1;k <= (ACAM::tot << 1);++k)
                    ret[i][j] = (ret[i][j] + (long long)a[i][k] * o[k][j]) % mod;
        return ret;
    }
} mat;
inline Matrix fpow(Matrix a,int b)
{
    Matrix ret(1);
    for(;b;b >>= 1)
        (b & 1) && (ret = ret * a,1),a = a * a;
    return ret;
}
int ans;
int main()
{
    scanf("%d%d%d",&n,&m,&l);
    for(register int i = 1;i <= n;++i)
        scanf("%s",s + len[i - 1] + 1),len[i] = len[i - 1] + strlen(s + len[i - 1] + 1);
    for(register int i = 1,len;i <= m;++i)
    {
        scanf("%s",t + 1),ACAM::las = 1,len = strlen(t + 1);
        for(register int j = 1;j <= len;++j)
            ACAM::insert(t[j] - 'a',j == len);
    }
    ACAM::get_fail();
    if(l <= M)
    {
        f[0][1] = 1;
        for(register int i = 0;i <= l;++i)
            for(register int j = 1;j <= ACAM::tot;++j)
                for(register int k = 1;k <= n;++k)
                    if(i + len[k] - len[k - 1] <= l)
                    {
                        int p = ACAM::match(s + len[k - 1],len[k] - len[k - 1],j);
                        if(p)
                            f[i + len[k] - len[k - 1]][p] = (f[i + len[k] - len[k - 1]][p] + f[i][j]) % mod;
                    }
        for(register int i = 1;i <= ACAM::tot;++i)
            ans = (ans + f[l][i]) % mod;
        printf("%d\n",ans);
        return 0;
    }
    for(register int i = 1;i <= n;++i)
        for(register int j = 1;j <= ACAM::tot;++j)
        {
            int p = ACAM::match(s + len[i - 1],len[i] - len[i - 1],j);
            if(p)
                ++mat[(len[i] - len[i - 1] == 1) * ACAM::tot + j][ACAM::tot + p];
        }
    for(register int i = 1;i <= ACAM::tot;++i)
        mat[ACAM::tot + i][i] = 1;
    mat = fpow(mat,l);
    for(register int i = 1;i <= ACAM::tot;++i)
        ans = (ans + mat[ACAM::tot + 1][ACAM::tot + i]) % mod;
    printf("%d\n",ans);
}