分析

本题目的状态表示$f[i][j]:长度为i,在自动机节点j上，不包含任何单词的方案数$
则答案为$ans=26^{m}-\sum f[m][i]\(长度为m在自动机节点i，不包含任何单词的方案数\)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110,M = 6e3+10,mod = 10007;
char s[N];
int tr[M][30],ne[M],idx;
int n,m,f[N][M],ans=1,temp;
int q[M],hh,tt;
bool st[M]; //判断该节点上是否有单词
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()    //构建AC自动机
{
    hh=0,tt=-1;
    for(int i=0;i<26;i++)
    {
        if(tr[0][i]){
            ne[tr[0][i]]=0;
            q[++tt]=tr[0][i];
        }
    }
    while(hh<=tt)   
    {
        auto t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int j=tr[t][i];
            if(!j) tr[t][i]=tr[ne[t]][i];   
            else{
                st[j]|=st[tr[ne[t]][i]];    //如果该点能走通，就将该点的st[]与其前继节点的st[]进行或运算
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        insert();
    }
    build();    //建立AC自动机

    f[0][0]=1;  //长度为0,在节点0(源点)上，不包含任何单词的方案数为1
    for(int i=1;i<=m;i++)   
    {
        for(int j=0;j<=idx;j++)
        {
            for(int k=0;k<26;k++)
            {
                if(!st[tr[j][k]])   //如果该点上面没有单词
                {
                    f[i][tr[j][k]]=(f[i][tr[j][k]]+f[i-1][j])%mod;  //状态累加
                }
            }
        }
    }

    for(int i=1;i<=m;i++) ans=(ans*26)%mod; //计算26^m
    for(int i=0;i<=idx;i++) temp=(temp+f[m][i])%mod;    //计算不含任何单词的方案总数

    cout<<(ans-temp+mod)%mod<<endl;   

    return 0;
}