其实这题的思路也大同小异，利用AC自动机建 trie 图之后，构建可达矩阵，可达矩阵 m 次方后，第一行的值就是答案。需要注意，这个题的答案很大，需要用到高精度，所以把高精度跟矩阵乘法结合即可。
如果单纯只是这样的话，先会 re 然后再 t，wa 是因为读入的字符串的范围是([33,255])，所以不能单纯用数组来存，需要用 map 来进行保存。
此外因为高精度乘法，再加上(n^3)的矩阵乘法，导致复杂度过大，所以会 t。观察发现，我们只用到了 ans 矩阵的第一行，所以可以只计算第一行的值即可，这样矩阵乘法就少了一个 n 的复杂度。
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;
int MAXN=9999;
const int maxsize=30;
int dlen=4;
class BigNum {
public:
int a[maxsize];
int len;
public:
BigNum() {
len = 1;
memset(a,0,sizeof(a));
}
BigNum(const int b) {
int c,d = b;
len = 0;
memset(a,0,sizeof(a));
while (d > MAXN) {
c = d - (d / (MAXN + 1)) * (MAXN + 1);
d = d / (MAXN + 1);
a[len++] = c;
}
a[len++] = d;
}
BigNum operator+(const BigNum & T) const {
BigNum t(*this);
int i,big;
big = T.len > len ? T.len : len;
for (i = 0 ; i < big ; i++) {
t.a[i] +=T.a[i];
if (t.a[i] > MAXN) {
t.a[i + 1]++;
t.a[i] -=MAXN+1;
}
}
if (t.a[big] != 0) t.len = big + 1;
else t.len = big;
return t;
}
BigNum operator*(const BigNum & T) const {
BigNum ret;
int i,j,up,temp,temp1;
for (i = 0 ; i < len ; i++) {
up = 0;
for (j = 0 ; j < T.len ; j++) {
temp = a[i] * T.a[j] + ret.a[i + j] + up;
if (temp > MAXN) {
temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
up = temp / (MAXN + 1);
ret.a[i + j] = temp1;
} else {
up = 0;
ret.a[i + j] = temp;
}
}
if (up != 0)
ret.a[i + j] = up;
}
ret.len = i + j;
while (ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
return ret;
}
};
ostream& operator<<(ostream& out,BigNum& b) {
int i;
cout<<b.a[b.len-1];
for(i=b.len-2; i>=0; --i) {
cout.width(dlen);
cout.fill('0');
cout<<b.a[i];
}
return out;
}
typedef vector<BigNum> vec;
typedef vector<vec> mat;
mat operator *(mat &a,mat &b){
mat ans(a.size(),vec(b[0].size(),0));
for(int i=0;i<=0;++i)
for(int j=0;j<b[0].size();++j)
for(int k=0;k<b.size();++k)
ans[i][j]=ans[i][j]+a[i][k]*b[k][j];
return ans;
}
const int maxn=105;
namespace ac {
const int chsiz=300;
int fail[maxn],end[maxn];
map<char,int> next[maxn];
int root,sz;
int newcode(char s[],int &slen) {
for(int i=0; i<slen; ++i)
next[sz][s[i]]=-1;
end[sz++]=0;
return sz-1;
}
void init(char s[],int &slen) {
sz=0;
root=newcode(s,slen);
}
void insert(char buf[],char s[],int &slen) {
int len=strlen(buf);
int now=root;
for(int i=0; i<len; ++i) {
if(next[now][buf[i]]==-1)
next[now][buf[i]]=newcode(s,slen);
now=next[now][buf[i]];
}
end[now]++;
}
void build(char s[],int &slen) {
queue<int> q;
fail[root]=root;
for(int i=0; i<slen; ++i) {
if(next[root][s[i]]==-1)
next[root][s[i]]=root;
else {
fail[next[root][s[i]]]=root;
q.push(next[root][s[i]]);
}
}
while(q.size()) {
int now=q.front();
q.pop();
end[now]|=end[fail[now]];
for(int i=0; i<slen; ++i) {
if(next[now][s[i]]==-1)
next[now][s[i]]=next[fail[now]][s[i]];
else {
fail[next[now][s[i]]]=next[fail[now]][s[i]];
q.push(next[now][s[i]]);
}
}
}
}
mat getmat(char s[],int &slen) {
mat ans(sz,vec(sz,0));
for(int i=0; i<sz; ++i) {
for(int j=0; j<slen; ++j)
if(!end[next[i][s[j]]])
ans[i][next[i][s[j]]]=ans[i][next[i][s[j]]]+1;
}
return ans;
}
}
char s[maxn],buf[maxn];
int main() {
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
scanf("%s",s);
ac::init(s,n);
for(int i=1; i<=p; ++i) {
scanf("%s",buf);
ac::insert(buf,s,n);
}
ac::build(s,n);
mat k=ac::getmat(s,n);
mat ans=k;
for(int i=1;i<m;++i)
ans=ans*k;
BigNum sum=0;
for(int i=0; i<ac::sz; ++i)
sum=sum+ans[0][i];
cout<<sum<<endl;
return 0;
}