這題還是挺經典的
首先的話，是建立自動機的過程。其實就是一個狀態的轉移，看一個字典樹中的某子串加上一個字母是否會變成一個非法的串，然後都給標記起來。
最後就看有多少種狀態，就建立多大的矩陣，對某種狀態，如果加上一個字母後是合法的，就把表示狀態可以轉移。對應的矩陣中的位置就++
然後就是矩陣乘了，乘了k次後的矩陣x[i][j] 就表示從i狀態到j狀態路徑轉移長度為k的個數 ，那最後的結果就是從0狀態到所有狀態的和了
需要注意的是取模運算耗費的時間很大，能盡量減少就減少這種操作。
[cpp]
include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 155
#define MAXM 40000
#define INF 1000000001
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int h[155];
int n, m, e;
long long mat[MAXN][MAXN], ans[MAXN][MAXN];
struct Trie
{
int next[4];
int fail, flag;
void init ()
{
memset(next, 0, sizeof(next));
fail = -1;
flag = 0;
}
} trie[MAXM];
void init()
{
for(int i = 0; i < MAXM; i++) trie[i].init();
e = 0;
memset(mat, 0, sizeof(mat));
memset(ans, 0, sizeof(ans));
}
void make_trie (char *str)
{
int i = 0, index, u = 0;
while(str[i])
{
index = h[str[i]];
if(!trie[u].next[index]) trie[u].next[index] = ++e;
u = trie[u].next[index];
i++;
}
trie[u].flag = 1;
}
int q[MAXM];
void make_ac_automation()
{
int h = 0, t = 0;
q[t++] = 0;
while(h < t)
{
int u = q[h++], v, j;
for(int i = 0; i < 4; i++)
{
if(trie[u].next[i])
{
v = trie[u].next[i];
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[v].fail = 0;
else
{
trie[v].fail = trie[j].next[i];
trie[v].flag |= trie[trie[v].fail].flag;
}
q[t++] = v;
}
else
{
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[u].next[i] = 0;
else trie[u].next[i] = trie[j].next[i];
}
}
}
}
long long z[MAXN][MAXN];
long long mod = 100000;
void multiply(long long x[MAXN][MAXN], long long y[MAXN][MAXN])
{
for(int i = 0; i <= e; i++)
{
for(int j = 0; j <= e; j++)
{
z[i][j] = 0;
for(int k = 0; k <= e; k++)
z[i][j] = z[i][j] + x[i][k] * y[k][j];
z[i][j] %= mod;
}
}
for(int i = 0; i <= e; i++)
for(int j = 0; j <= e; j++)
y[i][j] = z[i][j];
}
int main()
{
init();
h['A'] = 0, h['T'] = 1, h['G'] = 2, h['C'] = 3;
scanf("%d%d", &m, &n);
char str[25];
for(int i = 0; i < m; i++)
{
scanf("%s", str);
make_trie(str);
}
make_ac_automation();
for(int i = 0; i <= e; i++)
if(trie[i].flag == 0)
for(int j = 0; j < 4; j++)
if(trie[trie[i].next[j]].flag == 0)
mat[i][trie[i].next[j]]++;
for(int i = 0; i <= e; i++) ans[i][i] = 1;
while(n)
{
if(n & 1) multiply(mat, ans);
multiply(mat, mat);
n >>= 1;
}
long long res = 0;
for(int i = 0; i <= e; i++) res = res + ans[0][i];
printf("%I64d\n", res % mod);
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 155
#define MAXM 40000
#define INF 1000000001
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int h[155];
int n, m, e;
long long mat[MAXN][MAXN], ans[MAXN][MAXN];
struct Trie
{
int next[4];
int fail, flag;
void init ()
{
memset(next, 0, sizeof(next));
fail = -1;
flag = 0;
}
} trie[MAXM];
void init()
{
for(int i = 0; i < MAXM; i++) trie[i].init();
e = 0;
memset(mat, 0, sizeof(mat));
memset(ans, 0, sizeof(ans));
}
void make_trie (char *str)
{
int i = 0, index, u = 0;
while(str[i])
{
index = h[str[i]];
if(!trie[u].next[index]) trie[u].next[index] = ++e;
u = trie[u].next[index];
i++;
}
trie[u].flag = 1;
}
int q[MAXM];
void make_ac_automation()
{
int h = 0, t = 0;
q[t++] = 0;
while(h < t)
{
int u = q[h++], v, j;
for(int i = 0; i < 4; i++)
{
if(trie[u].next[i])
{
v = trie[u].next[i];
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[v].fail = 0;
else
{
trie[v].fail = trie[j].next[i];
trie[v].flag |= trie[trie[v].fail].flag;
}
q[t++] = v;
}
else
{
j = trie[u].fail;
while(j != -1 && !trie[j].next[i]) j = trie[j].fail;
if(j == -1) trie[u].next[i] = 0;
else trie[u].next[i] = trie[j].next[i];
}
}
}
}
long long z[MAXN][MAXN];
long long mod = 100000;
void multiply(long long x[MAXN][MAXN], long long y[MAXN][MAXN])
{
for(int i = 0; i <= e; i++)
{
for(int j = 0; j <= e; j++)
{
z[i][j] = 0;
for(int k = 0; k <= e; k++)
z[i][j] = z[i][j] + x[i][k] * y[k][j];
z[i][j] %= mod;
}
}
for(int i = 0; i <= e; i++)
for(int j = 0; j <= e; j++)
y[i][j] = z[i][j];
}
int main()
{
init();
h['A'] = 0, h['T'] = 1, h['G'] = 2, h['C'] = 3;
scanf("%d%d", &m, &n);
char str[25];
for(int i = 0; i < m; i++)
{
scanf("%s", str);
make_trie(str);
}
make_ac_automation();
for(int i = 0; i <= e; i++)
if(trie[i].flag == 0)
for(int j = 0; j < 4; j++)
if(trie[trie[i].next[j]].flag == 0)
mat[i][trie[i].next[j]]++;
for(int i = 0; i <= e; i++) ans[i][i] = 1;
while(n)
{
if(n & 1) multiply(mat, ans);
multiply(mat, mat);
n >>= 1;
}
long long res = 0;
for(int i = 0; i <= e; i++) res = res + ans[0][i];
printf("%I64d\n", res % mod);
return 0;
}
