第一次做这种题目，参考了下题解，相当于把树扯直了做DP，估计这一类题都是这个套路吧。
状态方程dp[i][next] = dp[i][next]+dp[i][j] ;dp[i][j]表示长度为i的第J个结点的时候满足题意的num，next为当前j点所能走到的下一个合法的结点。
需要用高精度，看到一些规范的高精度写法，觉得不错，有空整理下来。
不知道是不是我理解错了，按理说字符串病毒长度不应超过10.。但开到55依旧RE，开550AC。。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 110
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
const int child_num = ;
const int BASE = ;
const int DIG = ;
char s[N*],vir[];
int id[];
struct bignum
{
int a[],len;
bignum()
{
memset(a,,sizeof(a));
len = ;
}
bignum(int v)
{
memset(a,,sizeof(a));
len = ;
do
{
a[len++] = v%BASE;
v/=BASE;
}while(v);
}
/*bignum(const char s[])
{
memset(a,0,sizeof(a));
int k = strlen(s);
len = k/DIG;
if(k%DIG) len++;
int cnt = 0;
for(int i = k-1; i >= 0 ; i-=DIG)
{
int t = 0;
int kk = i-DIG+1;
if(kk<0) kk =0;
for(int j = kk ; j <= i ; j++)
t = t*10+s[j]-'0';
a[cnt++] = t;
}
}*/
bignum operator + (const bignum &b)const
{
bignum res;
res.len = max(len,b.len);
int i;
for(i = ; i < res.len ;i ++)
res.a[i] = ;
for(i = ; i < res.len ; i++)
{
res.a[i] += ((i<len)?a[i]:)+((i<b.len)?b.a[i]:);
res.a[i+] += res.a[i]/BASE;
res.a[i] = res.a[i]%BASE;
}
if(res.a[res.len]>) res.len++;
return res;
}
void output()
{
printf("%d",a[len-]);
for(int i = len- ; i >= ; i--)
printf("%04d",a[i]);
printf("\n");
}
}dp[][];
class AC
{
private:
int ch[N][child_num];
int Q[N];
int val[N];
int fail[N];
//int id[N];
int sz;
public :
void init()
{
fail[] = ;
//for(int i = 0 ;i < child_num-32 ; i++)
//id[i+32] = i;
}
void reset()
{
memset(val,,sizeof(val));
memset(fail,,sizeof(fail));
memset(ch[],,sizeof(ch[]));
sz = ;
}
void insert(char *a,int key)
{
int k = strlen(a),p = ;
for(int i = ; i < k ;i++)
{
int d = id[a[i]];
if(ch[p][d]==)
{
memset(ch[sz],,sizeof(ch[sz]));
ch[p][d] = sz++;
}
p = ch[p][d];
}
val[p] = key;
}
void construct(int n)
{
int i,head=,tail = ;
for(i = ; i < n ; i++)
{
if(ch[][i])
{
Q[tail++] = ch[][i];
fail[ch[][i]] = ;
}
}
while(head!=tail)
{
int u = Q[head++];
val[u]|=val[fail[u]];
for(i = ; i < n ; i++)
{
if(ch[u][i])
{
Q[tail++] = ch[u][i];
fail[ch[u][i]] = ch[fail[u]][i];
}
else ch[u][i] = ch[fail[u]][i];
}
}
}
void work(int m,int n)
{
int i,j,g;
for(i = ; i <= m ;i++)
for(j = ;j <= sz; j++)
dp[i][j] = bignum();
dp[][] = bignum();
for(i = ; i < m ;i++)
{
for(j = ; j < sz ;j++)
for(g = ; g < n ; g++)
if(!val[ch[j][g]])
{
dp[i+][ch[j][g]]=dp[i+][ch[j][g]]+dp[i][j];
}
}
bignum ans = bignum();
for(j = ;j < sz ; j++)
ans=ans+dp[m][j];
ans.output();
}
}ac;
int main()
{
int n,m,i,p;
ac.init();
while(cin>>n>>m>>p)
{
cin>>s;
for(i = ; i < n; i++)
id[s[i]] = i;
ac.reset();
for(i = ;i <= p; i++)
{
scanf("%s",vir);
ac.insert(vir,);
}
ac.construct(n);
ac.work(m,n);
}
return ;
}