题意
构造只包含 \(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#include #include #include 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 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\n", ans); return 0;}