题意：
给n。m，k ，再给出m个单词
问长度为n的字符串。至少在m个单词中含有k个的组成方案有多少种。
思路：
因为m最大是10，所以能够採取状压的思想
首先建立trie图，在每一个单词的结束节点标记一个mark=(1<<id)，id为单词的编号
然后须要注意的，对于每一个节点，应该顺着fail指针遍历一遍，
把全部的mark取一个并集。
由于就是假设单词出现包括的话，比方 she和he 我拿了she，事实上等于两个都拿了。
dp[i][j][k] i步在节点j状态k的方案数
然后就是一个四重循环了
应该是非常好理解的
最后遍历在n步时，各个节点。然后判一下状态是否里面拿了不少于k个物品的个数
做一个累加就是答案了！
做dp的时候 顺便滚动了一下
代码：
#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
#include"map"
#include"string"
#define inf 9999999
#define mod 20090717
using namespace std;
int triecont;
struct trie
{
int mark,id;
trie *next[27],*fail;
trie()
{
memset(next,0,sizeof(next));
fail=NULL;
mark=id=0;
}
};
trie *root,*node[123];
void init(char *v,int k)
{
trie *p=root;
for(int i=0; v[i]; i++)
{
int tep=v[i]-'a';
if(p->next[tep]==NULL)
{
p->next[tep]=new trie();
node[triecont]=p->next[tep];
p->next[tep]->id=triecont++;
}
p=p->next[tep];
}
p->mark|=(1<<k);
}
void getac()
{
queue<trie*>q;
q.push(root);
while(!q.empty())
{
trie *p;
p=q.front();
q.pop();
for(int i=0; i<26; i++)
{
if(p->next[i]==NULL)
{
if(p==root) p->next[i]=root;
else p->next[i]=p->fail->next[i];
}
else
{
if(p==root) p->next[i]->fail=root;
else p->next[i]->fail=p->fail->next[i];
q.push(p->next[i]);
trie *tep=p->next[i];
if(p!=root) p->next[i]->mark|=p->next[i]->fail->mark;
}
}
}
}
int judge(int x)
{
int ans=0;
for(int i=0; i<10; i++)
{
if(x&(1<<i)) ans++;
}
return ans;
}
__int64 dp[2][105][1025];
int main()
{
int n,m,num;
while(scanf("%d%d%d",&n,&m,&num),(n+m+num))
{
memset(node,0,sizeof(node));
triecont=0;
root=new trie();
node[triecont]=root;
root->id=triecont++;
if(num>m)
{
puts("0");
continue;
}
for(int i=0; i<m; i++)
{
char x[12];
scanf("%s",x);
init(x,i);
}
getac();
for(int j=0; j<triecont; j++) for(int k=0; k<(1<<m); k++) dp[0][j][k]=0;
dp[0][0][0]=1;
for(int i=1; i<=n; i++)
{
for(int j=0; j<triecont; j++) for(int k=0; k<(1<<m); k++) dp[i%2][j][k]=0;
for(int j=0; j<triecont; j++)
{
for(int k=0; k<(1<<m); k++)
{
if(dp[1-i%2][j][k]==0) continue;
for(int l=0; l<26; l++)
{
trie *p=node[j]->next[l];
int tep=p->mark|k;
dp[i%2][p->id][tep]+=dp[1-i%2][j][k];
if(dp[i%2][p->id][tep]>=mod) dp[i%2][j][tep]%=mod;
}
}
}
}
__int64 ans=0;
for(int i=0; i<triecont; i++)
{
for(int j=0; j<(1<<m); j++)
{
if(judge(j)>=num)
{
ans+=dp[n%2][i][j];
if(ans>=mod) ans%=mod;
}
}
}
printf("%I64d\n",ans%mod);
}
return 0;
}