[JSOI2007] 文本生成器

Trie图版的GT考试？
先建个trie图，如果trie上某节点的前缀上有标记，那这个点也不能走。
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 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<int>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 }