好题一道，推了一会，然后计算了一下时间复杂度，差不多最坏情况是25*100*1024*26=66560000然后看了下，嗯，能搞，有搞头哈哈哈，然后写了一下，首先……WA了，发现竟然是最大极限哪儿写错了，我的个天呐！A！
我们看到最多也就是10个单词，那么不如状压这十个单词吧，然后就从这十个单词开始做文章，我们不断的推状态，每个单词的尾记下它的状压状态，然后记得build_fail建立fail指针的时候要去更新状压状态——因为题目中有说可以重叠的。
然后就是dp，dp推的是方案数，dp[i][j][k]，我用以分别表示，目前i长度下、j状态（单词状态，后缀是哪个单词的情况）、k表示目前得到的状压状态。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int mod = 20090717;
int N, M, K, tot, _Index;
struct node
{
int nex[26], fail, val, id;
node() { memset(nex, 0, sizeof(nex)); fail = val = id = 0; }
void clear() { memset(nex, 0, sizeof(nex)); fail = val = id = 0; }
}trie[105];
char virus[15];
void insert(char *s, int id)
{
int len = (int)strlen(s), p = 0;
for(int i=0; i<len; i++)
{
int a = s[i] - 'a';
if(!trie[p].nex[a])
{
trie[++_Index].clear();
trie[p].nex[a] = _Index;
}
p = trie[p].nex[a];
}
trie[p].val++;
trie[p].id |= (1<<id);
}
void build_fail()
{
int p, son, temp;
queue<int> Q;
Q.push(0);
while(!Q.empty())
{
p = Q.front(); Q.pop();
for(int i=0; i<26; i++)
{
son = trie[p].nex[i];
if(son)
{
if(!p) trie[son].fail = 0;
else
{
temp = trie[p].fail;
while(temp && !trie[temp].nex[i]) temp = trie[temp].fail;
trie[son].fail = trie[temp].nex[i];
}
trie[son].id |= trie[trie[son].fail].id;
Q.push(son);
}
else trie[p].nex[i] = trie[trie[p].fail].nex[i];
}
}
}
int dp[30][105][1050];
bool check(int state)
{
int sum = 0;
for(int i=log2(1. * state); i>=0; i--) sum += ( (state>>i) & 1 );
return sum >= K;
}
void solve()
{
for(int i=0; i<=N; i++) for(int j=0; j<=_Index; j++) for(int k=0; k<=tot; k++) dp[i][j][k] = 0;
dp[0][0][0] = 1;
int ans = 0;
for(int i=0; i<N; i++)
{
for(int j=0; j<=_Index; j++)
{
for(int k=0; k<=tot; k++)
{
if(dp[i][j][k]) //以上————前一个状态
{
for(int f=0; f<26; f++)
{
int x = i + 1, y = trie[j].nex[f], z = trie[y].id|k;
dp[x][y][z] = (dp[x][y][z] + dp[i][j][k])%mod;
}
}
}
}
}
for(int i=0; i<=tot; i++)
{
if(!check(i)) continue;
for(int j=0; j<=_Index; j++) ans = (ans + dp[N][j][i])%mod;
}
printf("%d\n", ans);
}
inline void init()
{
_Index = 0;
tot = (1<<M) - 1;
trie[0].clear();
}
int main()
{
while(scanf("%d%d%d", &N, &M, &K) && (N | M | K))
{
init();
for(int i=0; i<M; i++)
{
scanf("%s", virus);
insert(virus, i);
}
build_fail();
solve();
}
return 0;
}
