传送门：点击打开链接
题意：有个密码长度为n，现在有m个魔力单词，要求密码中魔力单词的种类数>=k，问这种密码的种类数。
思路：和之前一样，我们会想到AC自动机去压缩状态，把状态给简化。然后我们就会想到一个问题，，因为一种种类实际上可能会出现很多次，但是统计的时候只统计一次，所以用普通的dp可能就做不到了，那么我们就必须考虑复杂度更高的方法，又看到m<=10,我们自然的想到了状压。因为一个节点可能是多个单词的结尾，所以用状压就刚好能表示出多个单词结尾的情况了，非常的巧妙~
但是这题也有两个很容易TLE的问题，，首先是一个超级剪枝，，虽然已经是第二次遇到这个问题了，但还是一开始没想到。
因为我们的dp是属于向前dp的类型，这种dp有一个非常好的优势，那就是如果当前状态的种类数为0，那么这个状态对后面就没有任何作用，可以直接剪枝。这样我们就能减去非常多的情况了。
其次，就是memset初始化的时候，如果组数比较多可能会超时，改成for循环去填充就行。。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;/*MX为总长度*/
const int MN = 25 + 5;
const int MX = 2e2 + 5;
const int mod = 20090717;
const int P = 26;LL dp[2][1 << 10][MX];struct AC_machine {int rear, root, m;int Next[MX][P], Fail[MX], End[MX];void Init(int _m) {m = _m;rear = 0;root = New();}int New() {End[rear] = 0;for(int i = 0; i < P; i++) {Next[rear][i] = -1;}return rear++;}void Add(char *A, int u) {int now = root, n = strlen(A);for(int i = 0; i < n; i++) {int id = A[i] - 'a';if(Next[now][id] == -1) {Next[now][id] = New();}now = Next[now][id];}End[now] |= 1 << u;}void Build() {queue<int>Q;Fail[root] = root;for(int i = 0; i < P; i++) {if(Next[root][i] == -1) {Next[root][i] = root;} else {Fail[Next[root][i]] = root;Q.push(Next[root][i]);}}while(!Q.empty()) {int u = Q.front(); Q.pop();End[u] |= End[Fail[u]];for(int i = 0; i < P; i++) {if(Next[u][i] == -1) {Next[u][i] = Next[Fail[u]][i];} else {Fail[Next[u][i]] = Next[Fail[u]][i];Q.push(Next[u][i]);}}}}LL Solve(int N, int K) {int cur = 0, cnxt = 1;for(int S = 0; S < (1 << m); S++) {for(int j = 0; j < rear; j++) {dp[cur][S][j] = 0;}}dp[cur][0][0] = 1;for(int i = 1; i <= N; i++) {for(int S = 0; S < (1 << m); S++) {for(int j = 0; j < rear; j++) {dp[cnxt][S][j] = 0;}}for(int S = 0; S < (1 << m); S++) {for(int j = 0; j < rear; j++) {if(dp[cur][S][j]) {for(int k = 0; k < P; k++) {int nxt = Next[j][k];dp[cnxt][S | End[nxt]][nxt] += dp[cur][S][j];dp[cnxt][S | End[nxt]][nxt] %= mod;}}}}swap(cur, cnxt);}LL ans = 0;for(int S = 0; S < (1 << m); S++) {int cnt = 0;for(int i = 0; i < m; i++) {if(S >> i & 1) cnt++;}if(cnt < K) continue;for(int j = 0; j < rear; j++) {ans += dp[cur][S][j];ans %= mod;}}return ans;}
} AC;char word[MX];int main() {int n, m, k; //FIN;while(~scanf("%d%d%d", &n, &m, &k), n) {AC.Init(m);for(int i = 0; i < m; i++) {scanf("%s", word);AC.Add(word, i);}AC.Build();printf("%I64d\n", AC.Solve(n, k));}return 0;
}