题目：传送门
题意： 给你m个病毒串，只由(A、G、T、C) 组成， 问你生成一个长度为 n 的 只由 A、C、T、G 构成的，不包含病毒串的序列的方案数。
解： 对 m 个病毒串，建 AC 自动机， 然后， 这个AC自动机就类似于一张有向图， 可以用邻接矩阵存这张有向图。
最多10个病毒串， 每个病毒串长度不超过 10， 那最多是个 100 * 100 的矩阵， 可以接受。
最后用矩阵快速幂加速推导。
#include<cstdio> #include<cstring> #include<queue> #define LL long long #define rep(i, j, k) for(int i = j; i <= k; i++) #define dep(i, j, k) for(int i = k; i >= j; i--) #define INF 0x3f3f3f3f #define inf 0x3f3f3f3f3f3f3f3f #define mem(i, j) memset(i, j, sizeof(i)) #define pb push_back using namespace std; const int N = 111, mod = 100000; struct mat { LL a[N][N]; mat() { mem(a, 0); } }; struct Trie { int ch[N][30], tot, metch[N], Fail[N]; void init() { mem(ch[0], 0); tot = 1; metch[0] = 0; } int get(char Q) { if(Q == 'A') return 0; else if(Q == 'C') return 1; else if(Q == 'T') return 2; return 3; } void join(char s[]) { int now = 0; int len = strlen(s); rep(i, 0, len - 1) { int id = get(s[i]); if(!ch[now][id]) { mem(ch[tot], 0); metch[tot] = 0; ch[now][id] = tot++; } now = ch[now][id]; } metch[now] = 1; } void getFail() { queue<int> Q; while(!Q.empty()) Q.pop(); rep(i, 0, 3) { if(ch[0][i]) { Q.push(ch[0][i]); Fail[ch[0][i]] = 0; } } while(!Q.empty()) { int now = Q.front(); Q.pop(); rep(i, 0, 3) { int u = ch[now][i]; if(u == 0) ch[now][i] = ch[Fail[now]][i]; else { Q.push(u); Fail[u] = ch[Fail[now]][i]; metch[u] |= metch[Fail[u]]; } } } } mat getMat() { mat A; rep(i, 0, tot - 1) { if(metch[i]) continue; rep(j, 0, 3) { if(!metch[ch[i][j]]) A.a[i][ch[i][j]]++; } } return A; } }; Trie AC; char b[25]; mat mul(mat A, mat B, int n) { mat C; rep(i, 0, n) { rep(j, 0, n) { rep(k, 0, n) { C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod; } } } return C; } mat ksm(mat A, int B, int n) { mat res; rep(i, 0, n) res.a[i][i] = 1; while(B) { if(B & 1) res = mul(res, A, n); A = mul(A, A, n); B >>= 1; } return res; } int main() { int n, m; while(~scanf("%d %d", &m, &n)) { AC.init(); rep(i, 1, m) { scanf("%s", b); AC.join(b); } AC.getFail(); mat A; A = AC.getMat(); mat ans = ksm(A, n, AC.tot - 1); LL res = 0LL; rep(i, 0, AC.tot - 1) { res = (res + ans.a[0][i]) % mod; } printf("%lld\n", res); } return 0; }