题解：
ac自动机+dp的题目
差不多都一个套路
记录枚举了i位，匹配到自动机上的x位，然后对于匹配了哪些单词状态压缩一下就可以了
代码：
#include <bits/stdc++.h>
using namespace std;
#define mo 20090717
int dp[27][250][1030],w[1000],c[500][27];
int cnt,fail[1000],pp[1030];
char s[1000009];
void insert(char s[1000009],int x)
{
int len=strlen(s),now=0;
for (int i=0;i<len;i++)
{
int v=s[i]-'a';
if (!c[now][v]) c[now][v]=++cnt;
now=c[now][v];
}
w[now]=1<<(x-1);
}
queue<int> q;
void build()
{
for (int i=0;i<26;i++)
if (c[0][i]) fail[c[0][i]]=0,q.push(c[0][i]);
while (!q.empty())
{
int u=q.front();q.pop();
for (int i=0;i<26;i++)
{
if (c[u][i])
{
fail[c[u][i]]=c[fail[u]][i];
q.push(c[u][i]);
} else c[u][i]=c[fail[u]][i];
w[c[u][i]]|=w[c[fail[u]][i]];
}
}
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
for (int i=1;i<=1028;i++)
{
int l=0;
for (int j=0;j<=10;j++)
if ((i>>j)%2==1) l++;
pp[i]=l;
}
int n,m,k;
while (cin>>n>>m>>k&&!(n==0&&m==0&&k==0))
{
memset(fail,0,sizeof(fail));
memset(c,0,sizeof(c));
memset(w,0,sizeof(w)); cnt=0;
for (int i=1;i<=m;i++)
{
cin>>s; insert(s,i);
}
build();
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
for (int i=0;i<=n;i++)
for (int j=0;j<=cnt;j++)
for (int k1=0;k1<=(1<<m)-1;k1++)
if (dp[i][j][k1])
for (int k2=0;k2<26;k2++)
{
int u=c[j][k2];
dp[i+1][u][k1|w[u]]+=dp[i][j][k1];
dp[i+1][u][k1|w[u]]%=mo;
}
/* for (int i=0;i<=n;i++)
for (int j=0;j<=cnt;j++)
for (int k1=1;k1<=(1<<m)-1;k1++)
if (dp[i][j][k1])
cout<<i<<" "<<j<<" "<<k1<<endl; */
int ans=0;
for (int i=0;i<=(1<<m)-1;i++)
if (pp[i]>=k)
for (int j=0;j<=cnt;j++)
{
ans+=dp[n][j][i];
ans%=mo;
}
cout<<ans<<" "<<cnt<<endl;
}
return 0;
}