Trie图版的？

先建个trie图，如果trie上某节点的前缀上有标记，那这个点也不能走。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define mod 10007 6 using namespace std; 7  8 int n,m,ans; 9 char str[105];10 int s[6005][30],tc;11 int ed[6005],fal[6005];12 13 void ins()14 {15     scanf("%s",str+1);16     int p=0;17     int l=strlen(str+1);18     for(int i=1;i<=l;i++)19     {20         int c=str[i]-'A'+1;21         if(!s[p][c])s[p][c]=++tc;22         p=s[p][c];23     }24     ed[p]++;25 }26 27 queue
         
          qq;28 29 void build()30 {31     qq.push(0);32     while(!qq.empty())33     {34         int p=qq.front();35         qq.pop();36         for(int i=1;i<=26;i++)37         {38             int lf=(!p)?0:s[fal[p]][i];39             if(s[p][i])40             {41                 fal[s[p][i]]=lf;42                 qq.push(s[p][i]);43                 ed[s[p][i]]|=ed[fal[s[p][i]]];44             }45             else s[p][i]=lf;46         }47     }48 }49 50 int f[105][6005];51 52 int main()53 {54     scanf("%d%d",&n,&m);55     for(int i=1;i<=n;i++)ins();56     build();57     f[0][0]=1;58     for(int i=1;i<=m;i++)59     {60         for(int j=0;j<=tc;j++)61         {62             if(!f[i-1][j])continue;63             for(int k=1;k<=26;k++)64             {65                 if(!ed[s[j][k]])66                     f[i][s[j][k]]=(f[i][s[j][k]]+f[i-1][j])%mod;67             }68         }69     }70     for(int i=0;i<=tc;i++)ans=(ans+f[m][i])%mod;71     int tot=1;72     for(int i=1;i<=m;i++)tot=(tot*26)%mod;73     printf("%d",((tot-ans)%mod+mod)%mod);74     return 0;75 }