题意：容易理解...
分析：在做这道题之前我做了hdu 4057，都是同一种类型的题，因为题中给的模式串的个数最多只能为10个，所以我们就很容易想到用状态压缩来做，但是开始的时候我的代码超时了dp时我们由dp[i][j][k]枚举其后接的字符转移到dp[i+1],在枚举前判断下是否有dp[i][j][k]=0，是的话可以直接continue，而不用再深一层循环.这样优化之后就没超时了。我用了滚动数组实现，其实这题可以不用滚动数组也可以过的，空间上不会卡。
代码实现：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int next[];
int fail;
int flag;
void init()
{
memset(next,,sizeof(next));
fail=;
flag=;
}
}a[];
char keyword[];
int tot,n,m,len;
int dp[][][<<]; void chushihua()
{
tot=;
a[].init();
memset(dp,,sizeof(dp));
} void insert(char *str,int biaohao)
{
int index,p=;
for(;*str!='\0';str++)
{
index=*str-'a';
if(a[p].next[index]==)
{
a[++tot].init();
a[p].next[index]=tot;
}
p=a[p].next[index];
}
a[p].flag=a[p].flag|(<<biaohao);
} void build_fail()
{
queue<int>Q;
int cur,p,son,i;
Q.push();
while(!Q.empty())
{
p=Q.front();
Q.pop();
for(i=;i<;i++)
{
if(a[p].next[i]!=)
{
son=a[p].next[i];
cur=a[p].fail;
if(p==)
a[son].fail=;
else
{
// while(cur&&a[cur].next[i]==0)
// cur=a[cur].fail;
a[son].fail=a[cur].next[i];
}
a[son].flag=a[son].flag|a[a[son].fail].flag;
Q.push(son);
}
else
a[p].next[i]=a[a[p].fail].next[i];
}
}
} int panduan(int x)
{
int i,s=;
for(;x;x=x>>)
if(x&)
s++;
if(s>=m)
return ;
else
return ;
} void solve()
{
int i,j,k,l,son,sum=,temp;
dp[][][]=;
for(i=;i<=len;i++)
{
memset(dp[&i],,sizeof(dp[&i]));//滚动数组
for(j=;j<=tot;j++)
for(l=;l<(<<);l++)
{
if(dp[&(i+)][j][l]==)//开始这里没加，果断超时了
continue;
for(k=;k<;k++)//开始的时候这层for循环和上一层for循环调换过来的，没有加那个if判断，导致超时了
{
son=a[j].next[k];
temp=l|a[son].flag;
dp[&i][son][temp]+=dp[&(i+)][j][l];
if(dp[&i][son][temp]>=)
dp[&i][son][temp]%=;
}
}
}
for(i=;i<=tot;i++)
for(j=;j<(<<);j++)
{
if(panduan(j))
sum=sum+dp[&len][i][j];
if(sum>=)
sum%=;
}
printf("%d\n",sum);
} int main()
{
int i;
while(scanf("%d%d%d",&len,&n,&m)!=EOF&&(len+n+m)!=)
{
chushihua();
getchar();
for(i=;i<n;i++)
{
scanf("%s",keyword);
insert(keyword,i);
}
build_fail();
solve();
}
return ;
}