好像这题的确只能用AC自动机做了……Aufun大佬太强啦

正着难我们反着做，用总共单词个数减去没有一个单词都不包含的

然后考虑怎么处理一个单词都不包含的，就是跑不到单词的结尾节点

定义$f[i][j]$为当前在自动机上$j$点且串长为$i$时的方案总数，然后只要从父亲往儿子不断转移就好了

顺便注意如果一个单词后缀是另一个单词那这个单词也不能走

话说好像SAM还是可以做啊，和AC自动机差不多的做法？不过懒得打了所以也不知道到底可不可以

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 using namespace std; 7 const int N=10005,mod=10007; 8 int ch[N][26],End[N],fail[N],f[105][N];char s[N]; 9 int n,m,tot,ans,sum;10 queue
         
           q;11 inline void init(){12     int u=0,len=strlen(s+1);13     for(int i=1;i<=len;++i){14         int x=s[i]-'A';15         if(!ch[u][x]) ch[u][x]=++tot;16         u=ch[u][x];17     }18     End[u]|=1;19 }20 void build(){21     for(int i=0;i<26;++i)22     if(ch[0][i]) q.push(ch[0][i]);23     while(!q.empty()){24         int u=q.front();q.pop();25         for(int i=0;i<26;++i){26             if(!ch[u][i]){27                 ch[u][i]=ch[fail[u]][i];continue;28             }29             End[ch[u][i]]|=End[ch[fail[u]][i]],30             fail[ch[u][i]]=ch[fail[u]][i];31             q.push(ch[u][i]);32         }33     }34 }35 inline int ksm(int x,int y){36     int res=1;37     while(y){38         if(y&1) (res*=x)%=mod;39         (x*=x)%=mod,y>>=1;40     }41     return res;42 }43 int main(){44 //    freopen("testdata.in","r",stdin);45     scanf("%d%d",&n,&m);46     for(int i=1;i<=n;++i)47     scanf("%s",s+1),init();48     build();49     f[0][0]=1;50     for(int i=1;i<=m;++i)51     for(int j=0;j<=tot;++j)52     for(int k=0;k<26;++k)53     if(!End[ch[j][k]]) (f[i][ch[j][k]]+=f[i-1][j])%=mod;54     for(int i=0;i<=tot;++i) (ans+=f[m][i])%=mod;55     sum=ksm(26,m);56     printf("%d\n",(sum-ans+mod)%mod);57     return 0;58 }