题意：给定A C G T 四种字符，给定长度n 问你长度为n的只包含这四种字符串 不包含模式串的数量有多少 ，给出m个有这四种字符组成的模式串
思路：给定n的数量为2e9级别，所以对于一次O（n）也无法解决，普通的遍历肯定不可行。长度为n的字符串，我们可知即是在trie树上经过（转移）n个节点获得的一个字符串，而要想这个字符串不包含我们之前给出的模式串，即等同于我们用给定的模式串构造一棵trie然后求解从根节点出发不经过模式串结尾节点的方法数有几种
离散数学中有结论是在一个图中求一个点i到另一个点j可达关系，只需要在该图的临接矩阵中做n次幂，即可得到从i走n步到达j有几种方法。因此只需要把trie数的临接矩阵求出，然后用矩阵快速幂求解即可。
ps ：这里注意build函数中，在每一次p的节点循环完成之后，我们要看当前p节点的fail指针指向的节点的标识状态，若fail指针指向的节点以某个模式串的尾结点，那么我们要相应的吧当前这个p点设置为不可到达的点，否则就会通过这个p点到某模式串的尾结点。（即end[p] |= end[fail[p]];）
AC代码：
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <cstdio> #include <map> using namespace std; typedef long long ll; const int MOD = 1e5; const int MAX_TOT = 107; const int MAXN = 17; int m,n; std::map<char,int>mp;//用一个map实现ACGT 到 0123的映射 这样next只需要开4个节点即可 //矩阵快速幂 struct Matrix { int mat[MAX_TOT][MAX_TOT],n; Matrix(){} Matrix(int num){ n = num; for(int i = 0;i < n;i ++){ for(int j = 0;j < n;j ++) mat[i][j] = 0; } } }; Matrix mul(Matrix a,Matrix b) { Matrix tmp = Matrix(a.n); for(int i = 0;i < a.n;i ++){ for(int j = 0;j < a.n;j ++){ for(int k = 0;k < a.n;k ++){ int sum = (ll)a.mat[i][k]*b.mat[k][j]%MOD; tmp.mat[i][j] = (tmp.mat[i][j] + sum)%MOD; } } } return tmp; } Matrix quickpow(Matrix a,ll n) { Matrix E = Matrix(a.n); for(int i = 0;i < a.n;i ++) E.mat[i][i] = 1; while(n){ if(n&1) E = mul(E,a); a = mul(a,a); n >>= 1; } return E; } // struct Aca { int Next[MAX_TOT][4],fail[MAX_TOT],end[MAX_TOT],size; queue<int>q; void init() { mp['A'] = 0,mp['C'] = 1,mp['T'] = 2,mp['G'] = 3; while(!q.empty()) q.pop(); for(int i = 0;i < MAX_TOT;i ++){ end[i] = fail[i] = 0; for(int ii = 0;ii < 4;ii ++) Next[i][ii] = 0; } size = 1; } void insert(char *s) { int len = strlen(s); int p = 1; for(int i = 0;i < len;i ++){ int c = mp[s[i]]; //printf("%d\n",c); if(!Next[p][c]) Next[p][c] = ++size; p = Next[p][c]; } end[p] = 1; } void build() { for(int i = 0;i < 4;i ++) Next[0][i] = 1; q.push(1); fail[1] = 0; while(!q.empty()){ int p = q.front(); q.pop(); for(int i = 0;i < 4;i ++){ int now = Next[p][i]; int fafail = fail[p]; if(!now){ Next[p][i] = Next[fafail][i]; continue; } fail[now] = Next[fafail][i]; q.push(now); } // 下一层不是结尾节点的点 如果他的fail指向了一个结尾节点 那么代表如果走到了这个节点失配 //的话 会走到fail处 因为fail是尾结点 所以当前失配位置也应当看做尾结点 end[p] |= end[fail[p]];//这有一个 end关系的传递要看到 wa吐了 } } Matrix getmartix()//获得trie树的临接矩阵 { Matrix tmp = Matrix(size); for(int i = 1;i <= size;i ++){ for(int j = 0;j < 4;j ++){ if(end[Next[i][j]]) continue;//这个点不可到达 因为他是尾结点 tmp.mat[i-1][Next[i][j]-1]++;//邻接矩阵可到达 } } return tmp; } }aca; //输出矩阵检查用的 void opMatrix(Matrix a) { for(int i = 0;i < a.n;i ++){ for(int j = 0;j < a.n;j ++){ printf(j == a.n-1?"%d\n":"%d ",a.mat[i][j]); } } } void debug(){ for(int i = 1;i <= aca.size;i ++){ printf("---fail = %d\n",aca.fail[i]); } } int main() { char s[MAXN]; aca.init(); scanf("%d%d",&m,&n); for(int i = 1;i <= m;i ++){ scanf("%s",s); aca.insert(s); } aca.build(); //debug(); Matrix res = aca.getmartix(); res = quickpow(res,n); //printf("-------------\n"); //opMatrix(res); //printf("-------------\n"); int ans = 0; for(int i = 0;i < res.n;i ++){ ans = (ans + res.mat[0][i])%MOD; } printf("%d\n",ans); return 0; }