题目描述

给我们许多字典串,让我们构造一个长度为M的串,其中至少包含一个字典串,问一共有多少方案数?

样例

输入

2 2
A
B

输出

100

分析

至少包含一个字符串不好直接求,我们可以求反面(不包含任何字典串),然后用所有情况减去反面情况.
AC自动机+DP
用f[i][j]表示当前枚举到第i位,匹配到Trie树上的第j个节点且没有走到非法节点的方案数
什么是非法节点:
1.字典串的终止节点一定是非法节点
2.如果一个节点的fail链上有非法节点,则该节点也是非法节点

AC自动机+DP

#include<bits/stdc++.h>
using namespace std;
const int N = 6010,mod = 10007;
int tr[N][26],st[N],idx;
int fail[N];
int q[N];
int f[N][N],d[N][N];
int n,m;
char s[N];
int qmi(int a,int b,int p)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
void insert()
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int t=s[i]-'A';
        if(!tr[p][t])tr[p][t]=++idx;
        p=tr[p][t];
    }
    st[p]=1;
}
void build()
{
    int hh=0,tt=0;
    for(int i=0;i<26;i++)
        if(tr[0][i])q[tt++]=tr[0][i];
    while(hh!=tt)
    {
        int t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int u=tr[t][i];
            if(!u)tr[t][i]=tr[fail[t]][i];
            else
            {
                fail[u]=tr[fail[t]][i];
                q[tt++]=u;
                st[u]|=st[fail[u]];
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        insert();
    }
    build();
    f[0][0]=1;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<=idx;j++)
        {
            for(int k=0;k<26;k++)
            {
                int u=tr[j][k];
                if(st[u])continue;
                else f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
            }
        }
    }
    int res=0;
    for(int i=0;i<=idx;i++)res=(res+f[m][i])%mod;
    res=((qmi(26,m,mod)-res)%mod+mod)%mod;
    cout<<res;
    return 0;
}