BZOJ 1030 TRIE図+DP
13745 ワード
問題を論じているようですね?、
面白い感じがして、書くのも簡単です.の
http://files.cnblogs.com/proverbs/Trie%E5%9B%BE%E7%9A%84%E6%9E%84%E5%BB%BA_%E6%B4%BB%E7%94%A8%E4%B8%8E%E6%94%B9%E8%BF%9B.pdf
View Code
面白い感じがして、書くのも簡単です.の
http://files.cnblogs.com/proverbs/Trie%E5%9B%BE%E7%9A%84%E6%9E%84%E5%BB%BA_%E6%B4%BB%E7%94%A8%E4%B8%8E%E6%94%B9%E8%BF%9B.pdf
View Code
1 #include <cstring>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <iostream>
5 #include <algorithm>
6
7 #define N 111
8 #define MOD 10007
9
10 using namespace std;
11
12 struct TR
13 {
14 int son[26]; bool fg; int f;
15 }tr[N*N];
16
17 int n,cnt,m,ans;
18 int q[N*N];
19 char str[N];
20 int dp[N][N*N][2];
21
22 inline void insert(char *s)
23 {
24 int len=strlen(s+1);
25 int now=1;
26 for(int i=1;i<=len;i++)
27 {
28 if(!tr[now].son[s[i]-'A']) tr[now].son[s[i]-'A']=++cnt;
29 now=tr[now].son[s[i]-'A'];
30 }
31 tr[now].fg=true;
32 }
33
34 inline void build()
35 {
36 int h=1,t=1,sta; q[1]=1;
37 while(h<=t)
38 {
39 sta=q[h++];
40 for(int i=0;i<26;i++)
41 {
42 int now=tr[sta].son[i],tmp;
43 if(sta==1) tmp=1;
44 else tmp=tr[tr[sta].f].son[i];
45 if(now==0) tr[sta].son[i]=tmp;
46 else
47 {
48 tr[now].f=tmp;tr[now].fg|=tr[tmp].fg;
49 q[++t]=now;
50 }
51 }
52 }
53 }
54
55 inline void read()
56 {
57 cnt=1; tr[1].f=1;
58 scanf("%d%d",&n,&m);
59 for(int i=1;i<=n;i++)
60 {
61 scanf("%s",str+1);
62 insert(str);
63 }
64 build();
65 }
66
67 inline void go()
68 {
69 dp[0][1][0]=1;
70 for(int i=0;i<m;i++)
71 for(int j=1;j<=cnt;j++)
72 {
73 if(dp[i][j][0])
74 {
75 for(int k=0;k<26;k++)
76 {
77 if(tr[tr[j].son[k]].fg) dp[i+1][tr[j].son[k]][1]=(dp[i+1][tr[j].son[k]][1]+dp[i][j][0])%MOD;
78 else dp[i+1][tr[j].son[k]][0]=(dp[i+1][tr[j].son[k]][0]+dp[i][j][0])%MOD;
79 }
80 }
81 if(dp[i][j][1])
82 {
83 for(int k=0;k<26;k++)
84 dp[i+1][tr[j].son[k]][1]=(dp[i+1][tr[j].son[k]][1]+dp[i][j][1])%MOD;
85 }
86 }
87 for(int i=1;i<=cnt;i++) ans=(ans+dp[m][i][1])%MOD;
88 printf("%d
",ans);
89 }
90
91 int main()
92 {
93 read(),go();
94 return 0;
95 }