poj2778
题意
构造只包含 (A, T, C, G) 的字符串,且满足不出现指定的一些字符串,问长度为 (n) 的字符串有多少种 ?
分析
AC 自动机 + 矩阵快速幂的神题 ,知识点很多。。。
AC 自动机为了给不同的状态之间建边,矩阵快速幂是为了加速状态转移。
比如说一共有 (5) 个状态,我要从 状态 (0) 转移到 状态 (4) ,从 (0) 出发,可以先转移到 (0) 再转移到 (4) ,也可以先转移到 (1) 再转移到 (4) ,后面类似。
建一个邻接矩阵,(mat[i][j]) 表示 (i) 转移到 (j) 的方案数,想象一下矩阵相乘的情况,(mat[0][4]) 的计算过程,神奇。。。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int MAXN = 105;
const int MOD = 1e5;
int n, m;
struct Matrix {
ll mat[MAXN][MAXN];
void init() {
memset(mat, 0, sizeof mat);
}
};
Matrix operator*(Matrix A, Matrix B) {
Matrix C;
C.init();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
for(int k = 0; k < n; k++) {
C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
}
}
}
return C;
}
Matrix operator^(Matrix A, int x) {
Matrix B;
B.init();
for(int i = 0; i < n; i++) B.mat[i][i] = 1;
while(x) {
if(x & 1) B = B * A;
A = A * A;
x >>= 1;
}
return B;
}
struct Trie {
int id[100];
int root, L, nxt[MAXN][4], val[MAXN], fail[MAXN];
int newnode() {
for(int i = 0; i < 4; i++) {
nxt[L][i] = -1;
}
return L++;
}
void init() {
id['A'] = 0; id['T'] = 1; id['C'] = 2; id['G'] = 3;
L = 0;
root = newnode();
memset(val, 0, sizeof val);
}
void insert(char s[15]) {
int len = strlen(s);
int now = root;
for(int i = 0; i < len; i++) {
int d = id[s[i]];
if(nxt[now][d] == -1) nxt[now][d] = newnode();
now = nxt[now][d];
}
val[now] = 1;
}
void build() {
queue<int> Q;
for(int i = 0; i < 4; i++) {
if(nxt[root][i] == -1) nxt[root][i] = root;
else {
fail[nxt[root][i]] = root;
Q.push(nxt[root][i]);
}
}
while(!Q.empty()) {
int now = Q.front(); Q.pop();
if(val[fail[now]]) val[now] = 1;
for(int i = 0; i < 4; i++) {
if(nxt[now][i] == -1) nxt[now][i] = nxt[fail[now]][i];
else {
fail[nxt[now][i]] = nxt[fail[now]][i];
Q.push(nxt[now][i]);
}
}
}
}
Matrix buildMatrix() {
Matrix A; A.init();
for(int i = 0; i < L; i++) {
for(int j = 0; j < 4; j++) {
if(!val[i] && !val[nxt[i][j]]) {
A.mat[i][nxt[i][j]]++;
}
}
}
return A;
}
}trie;
int main() {
trie.init();
int k;
scanf("%d%d", &m, &k);
for(int i = 0; i < m; i++) {
char s[15];
scanf("%s", s);
trie.insert(s);
}
trie.build();
Matrix A = trie.buildMatrix();
n = trie.L;
A = A ^ k;
int ans = 0;
for(int i = 0; i < n; i++) {
ans = (ans + A.mat[0][i]) % MOD;
}
printf("%d
", ans);
return 0;
}