HDU 2825 Wireless Password

题目链接：HDU-2825
题意：给出m个单词，要构造出满足包含其中大于等于k个单词的字符串，字符只包括小写字母，问长度为n的这样的串有多少个。
思路：令dp[i][j][k]表示当前已经构造了i个字符，在ac自动机上跑到结点j，且单词状态为k情况下的方案数。从dp[i][j][k]向dp[i+1]递推。注意单词可能重复出现。
代码：
  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<vector>
  4 #include<set>
  5 #include<cstring>
  6 #include<algorithm>
  7 #include<cmath>
  8 #include<iostream>
  9 #include<queue>
 10 using namespace std;
 11 typedef long long LL;
 12 const LL MAXN=2e3+10;
 13 const LL INF=0x3f3f3f3f;
 14 const LL MOD=20090717;
 15 
 16 struct AC
 17 {
 18     int ch[MAXN][26];
 19     vector<int> val[MAXN];
 20     int sz;
 21     AC() { init(); }
 22     void init() { sz=1; memset(ch[0],0,sizeof(ch[0])); val[0].clear();}
 23     int idx(char c)
 24     {
 25         return c-'a';
 26     }
 27     void insert(char *s,int v)
 28     {
 29         int u=0,n=strlen(s);
 30         for(int i=0;i<n;i++)
 31         {
 32             int c=idx(s[i]);
 33             if(!ch[u][c])
 34             {
 35                 memset(ch[sz],0,sizeof(ch[sz]));
 36                 val[sz].clear();
 37                 ch[u][c]=sz++;
 38             }
 39             u=ch[u][c];
 40         }
 41         val[u].push_back(v);
 42     }
 43     int f[MAXN];
 44     int last[MAXN];
 45     void getFail()
 46     {
 47         queue<int> q;
 48         f[0]=0;
 49         for(int c=0;c<26;c++)
 50         {
 51             int u=ch[0][c];
 52             if(u) {f[u]=0;q.push(u);last[u]=0;}
 53         }
 54         while(!q.empty())
 55         {
 56             int r=q.front();q.pop();
 57             for(int c=0;c<26;c++)
 58             {
 59                 int u=ch[r][c];
 60                 if(!u)
 61                 {
 62                     ch[r][c]=ch[f[r]][c];
 63                     continue;
 64                 }
 65                 q.push(u);
 66                 int v=f[r];
 67                 while(v && !ch[v][c]) v=f[v];
 68                 f[u]=ch[v][c];
 69                 last[u]=(val[f[u]].size())?f[u]:last[f[u]];
 70             }
 71         }
 72     }
 73 };
 74 AC T;
 75 int f[2][300][3000];
 76 bool isOK(int x,int k)
 77 {
 78     int sum=0;
 79     for(int i=1;i<=10;i++)
 80         if(x&(1<<i))
 81             sum++;
 82     return sum>=k;
 83 }
 84 int main()
 85 {
 86 #ifdef LOCAL
 87     freopen("in.txt","r",stdin);
 88     // freopen("out.txt","w",stdout);
 89 #endif
 90     int n,m,K;
 91     while(scanf("%d%d%d",&n,&m,&K)!=EOF && (n || m || K))
 92     {
 93         T.init();
 94         for(int i=1;i<=m;i++)
 95         {
 96             char s[100];
 97             scanf("%s",s);
 98             T.insert(s,i);
 99         }
100         T.getFail();
101         memset(f,0,sizeof(f));
102         f[0][0][0]=1;
103         for(int i=0;i<n;i++)
104         {
105             for(int j=0;j<T.sz;j++)
106                 for(int k=0;k<(1<<(m+1));k++)
107                     f[1-i%2][j][k]=0;
108             for(int j=0;j<T.sz;j++)
109                 for(int k=0;k<(1<<(m+1));k++)
110                     if(f[i%2][j][k])
111                         for(int jj=0;jj<26;jj++)
112                         {
113                             int v= T.ch[j][jj];
114                             int kk=k;
115                             if(T.val[v].size())
116                             {
117                                 for(unsigned int ii=0;ii<T.val[v].size();ii++)
118                                 {
119                                     if((kk&(1<<T.val[v][ii]))==0)
120                                         kk+=(1<<T.val[v][ii]);
121                                 }
122                             }
123                             while(T.last[v]!=0)
124                             {
125                                 v=T.last[v];
126                                 if(T.val[v].size())
127                                 {
128                                     for(unsigned int ii=0;ii<T.val[v].size();ii++)
129                                     {
130                                         if((kk&(1<<T.val[v][ii]))==0)
131                                             kk+=(1<<T.val[v][ii]);
132                                     }
133                                 }
134                             }
135                             v=T.ch[j][jj];
136                             f[(i+1)%2][v][kk]=(f[i%2][j][k]+f[(i+1)%2][v][kk])%MOD;
137                         }
138         }
139         int ans=0;
140         for(int i=0;i<T.sz;i++)
141             for(int k=0;k<(1<<(m+1));k+=2)
142                 if(isOK(k,K))
143                     ans=(ans+f[n%2][i][k])%MOD;
144         printf("%d
",ans);
145     }
146     return 0;
147 }