Description
It's well known that DNA Sequence is a sequence only contains A, C, T and G, and it's very useful to analyze a segment of DNA Sequence，For example, if a animal's DNA sequence contains segment ATC then it may mean that the animal may have a genetic disease. Until now scientists have found several those segments, the problem is how many kinds of DNA sequences of a species don't contain those segments.
Suppose that DNA sequences of a species is a sequence that consist of A, C, T and G，and the length of sequences is a given integer n.
Input
First line contains two integer m (0 <= m <= 10), n (1 <= n <=2000000000). Here, m is the number of genetic disease segment, and n is the length of sequences.
Next m lines each line contain a DNA genetic disease segment, and length of these segments is not larger than 10.
Output
An integer, the number of DNA sequences, mod 100000.
Sample Input
4 3
AT
AC
AG
AA
Sample Output
36 题目大意：给定n个病毒序列，求长度为m的序列里面不含有这n种病毒序列的有多少种。
思路：参考了https://blog.csdn.net/qq_36346262/article/details/76355416 题目是求长度为m的序列 那我们可以看成是从根节点出发往下走了m步之后到达字典树上的某一个节点，而最后求得就是从根节点走了m步之后能够到达的某个节点的种类数和，当然我们在走的时候需要避开病毒，也就是不能到达我们树中被标记过的点。最后就将这个问题转化成了求从根节点出发走m步之后到达任意一个k节点的种类数，可以用矩阵快速幂来求解。
ps：假如有一个矩阵mp[i][j]代表了从i节点走一步走到j节点的种类数，那么我们就用(mp[i][j])^n代表从i节点走n步之后到达j节点的种类数；
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue> using namespace std;
typedef long long LL;
const int max_tot = ;
const int max_size = ;
const LL mod = ;
char s[];
struct mac {
LL a[][];//由于只有小于等于10个单词且每个单词长度不超过10，所以最多有100个节点
int len;
mac() {
len = ;
memset(a, , sizeof(a));
}
mac operator*(const mac &c)const {
mac t; t.len = len;
for (int i = ; i < len; i++)
for (int j = ; j < len; j++) {
t.a[i][j] = ;
for (int k = ; k < len; k++)
t.a[i][j] += a[i][k] * c.a[k][j];
t.a[i][j] %= mod;
}
return t;
}
};
mac Pow(mac a, int b){
mac ans; ans.len = a.len;
for (int i = ; i < a.len; i++)ans.a[i][i] = ;
while (b) {
if (b & )
ans = ans*a;
a = a * a;
b >>= ;
}
return ans;
}
struct AC {
int trie[max_tot][max_size];
int val[max_tot];
int fail[max_tot], last[max_tot];
int size;
void Clear()
{
memset(trie[], , sizeof(trie[]));
size = ;
}
int idx(char x) {
if (x == 'A')return ;
if (x == 'C')return ;
if (x == 'G')return ;
if (x == 'T')return ;
}
void insert(char *str) {
int k = ;
for (int i = ; str[i]; i++) {
int x = idx(str[i]);
if (!trie[k][x]) {
memset(trie[size], , sizeof(trie[size]));
val[size] = ;
trie[k][x] = size++;
}
k = trie[k][x];
}
val[k] = ;
}
void GetFail()
{
queue<int>Q;
fail[] = ; int k = ;
for (int i = ; i < max_size; i++) {//计算第一层的fail指针跟last指针
k = trie[][i];
if (k) {
Q.push(k);
fail[k] = ;
last[k] = ;
}
}
while (!Q.empty()) {
int r = Q.front(); Q.pop();
for (int i = ; i < max_size; i++) {
k = trie[r][i];
if (!k) {
trie[r][i] = trie[fail[r]][i];
val[r] = val[r] || val[fail[r]];
continue;
}
Q.push(k);
int v = fail[r];
while (v && !trie[v][i])v = fail[k];
fail[k] = trie[v][i];
last[k] = (val[fail[k]] ? fail[k] : last[fail[k]]);
}
}
}
}ac;
int main()
{
ios::sync_with_stdio(false);
int n, m;
while (cin>>n>>m) {
ac.Clear();
for (int i = ; i <= n; i++) {
cin >> s;
ac.insert(s);
}
ac.GetFail();
mac ans; ans.len = ac.size;
for (int i = ; i < ac.size; i++) {
for (int j = ; j < max_size; j++) {
int u = ac.trie[i][j];
if (!ac.val[u])ans.a[i][u]++;
}
}
ans = Pow(ans, m);
LL sum = ;
for (int i = ; i < ; i++)
sum = (sum + ans.a[][i]) % mod;
cout << sum << endl;
}
return ;
}