邻接矩阵A = mp[i][j]表示从 i 到 j 的方案数, A^n 表示点与点之间走n步到达的方案数。
去除矩阵中有病毒的行和列,对 mp[0][ i ] 求和,0<=i<cnt 。有cnt - 1 个结点。
如何去除呢?显然需要标记,这里标记数组tag[ ],有两种情况需要标记(去除
1. 病毒序列尾结点显然要去除。
2. 若当前结点的fail[ ]结点为病毒,则当前结点也要去除。fail[ now ]表示的结点是 now的最大后缀
举个栗子,图中有五个结点,病毒序列ATCG和TC, 2号结点fail为5,3号结点fail为6.
按照第一种情况 结点 4,6显然被标记了,而3号结点的 fail 结点6是病毒,所以3号结点 就是病毒
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int maxn = 1005;
const int mod = 100000;
int trie[maxn][5]; //字典树
int cntword[maxn]; //记录该单词出现次数
int fail[maxn]; //失败时的回溯指针
int cnt = 0;//结点个数
int mp[128];
bool tag[maxn];//表示结点是否为病毒
struct Mat {
ll m[105][105];
};
int n;
Mat mul(Mat x,Mat y) {
Mat c;
for(int i=0; i<cnt; i++) {
for(int j=0; j<cnt; j++) {
c.m[i][j] = 0;
}
}
for(int i=0; i<cnt; i++) {
for(int j=0; j<cnt; j++) {
for(int k=0; k<cnt; k++) {
c.m[i][j] = (c.m[i][j]+ x.m[i][k]*y.m[k][j]);
}
c.m[i][j]%=mod;
}
}
return c;
}
Mat pow(Mat x,int y) { //求矩阵x的y次幂
Mat ans;
for(int i=0; i<cnt; i++)
for(int j=0; j<cnt; j++)
if(i==j)ans.m[i][i] = 1;
else ans.m[i][j] = 0;//防止多次输入,清零
while(y) {
if(y&1)ans = mul(ans,x);
x = mul(x,x);
y>>=1;
}
return ans;//返回ans
}
void insertWords(char s[],int len) {
int root = 0;
for(int i=0; i<len; i++) {
int next = mp[s[i]];
if(trie[root][next]==0) {
trie[root][next] = cnt,cnt++;
}
root = trie[root][next];
}
tag[root] = true;
}
void getFail() {
queue <int>q;
while(!q.empty())q.pop();
for(int i=1; i<5; i++) { //将第二层所有出现了的字母扔进队列
if(trie[0][i]) {
fail[trie[0][i]] = 0;
q.push(trie[0][i]);
}
}
//fail[now] ->当前节点now的失败指针指向的地方
////tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i=1; i<5; i++) {
if(trie[now][i]) {
fail[trie[now][i]] = trie[fail[now]][i];
q.push(trie[now][i]);
} else {
trie[now][i] = trie[fail[now]][i];
tag[now] = tag[now]||tag[fail[now]];
//后缀为病毒则now为病毒
}
}
}
}
void query() {
Mat m1;
for(int i=0; i<cnt; i++) {
for(int j=0; j<cnt; j++) {
m1.m[i][j] = 0;
}
}
ll as = 0;
for(int i=0; i<cnt; i++) { //遍历文本串
if(!tag[i]) {
for(int j=1; j<5; j++) {
if((!tag[trie[i][j]])) {
m1.m[i][trie[i][j]]++;//m1[i][j] 表示 i 到 j 一步有多少种走法
}
}
}
}
m1 = pow(m1,n);
for(int i=0; i<cnt; i++) {
as=(as+m1.m[0][i]);
}
printf("%lld\n",as%mod);
}
char s[12];
int main() {
int nn;
mp['A'] = 1;
mp['C'] = 2;
mp['T'] = 3;
mp['G'] = 4;
scanf("%d %d",&nn,&n);
memset(trie,0,sizeof(trie));
memset(tag,false,sizeof(tag));
cnt = 1;
for(int i=0; i<nn; i++) {
scanf("%s",s) ;//输入单词
insertWords(s,strlen(s));
}
fail[0] = 0;
getFail();
query();
return 0;
}
/*
12 2000000000
A
AT
AT
TT
CC
AG
ATCGG
CTAA
GTCA
GTCA
ATC
CTG
*/