题目大意：给定一个字符串长度与一个字符串集，求存在该集合中元素作为子串的该长度字串数量

思路：AC自动机+DP+容斥（全集-不合法的）

#include"cstdio"#include"cstring"#include"iostream"#include"algorithm"using namespace std;const int MAXN=65;const int MAXM=105;const int siz=26;const int MOD=1e4+7;int n,m,cnt,ans;int q[MAXN*MAXM];int f[MAXM][MAXN*MAXM];char ch[MAXM];struct Trie{    int vis,fail;    int sn[siz];}T[MAXN*MAXM];void ins(char *ch){    int ln=strlen(ch+1),nw=0;    for(int i=1;i<=ln;++i){        if(!T[nw].sn[ch[i]-'A']) T[nw].sn[ch[i]-'A']=++cnt;        nw=T[nw].sn[ch[i]-'A'];    }T[nw].vis=1;    return;}void Getfail(){    int hd=1,tl=0;    for(int i=0;i
    
     =MOD) f[i+1][T[j].sn[k]]-=MOD;                }            }        }    }for(int i=0;i<=cnt;++i) ans=(ans+f[m][i])%MOD;    return;}int Fpw(int a,int b){    int x=1;    while(b){        if(b&1) x=x*a%MOD;        b>>=1;a=a*a%MOD;    }return x;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;++i) scanf("%s",ch+1),ins(ch);    Getfail();f[0][0]=1;    DP();ans=(Fpw(26,m)-ans+MOD)%MOD;    printf("%d\n",ans);    return 0;}