题意：检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
非常有趣的题，利用ac自动机构建一个邻接矩阵，横纵坐标是ac自动机中的每一个点。
将从一个点经过一步可以到达的点连接起来，类似于1*2的矩形方块填长矩形的题，只不过那道题的状态转移方法不大相同。
1.①如果某一点向下有某一字母，则该点向下连接到对应的点；
②如果该点向下没有但其fail向下有，则连接到fail下对应的点；
③如果都没有，连接到0下的该字母对应的点，即重新开始循环。
2.把不可取的点从矩阵中去掉(入或出该点的路清零)。（也可以在构建矩阵时去掉。参考的题解中的代码是在构建矩阵前在矩阵中去掉以节省时间，我也是这么写的。）
3.矩阵快速幂求出0走n条路到各个点的路的数量。
虽然搞了一段时间但是整体来说并不是一道细节题，思路比较重要
代码如下
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 const int maxn=10010; 5 const double eps=1e-8; 6 const long long modn=100000; 7 int m,n; 8 struct mat{ 9 long long ma[110][110]; 10 mat(){ memset(ma,0,sizeof(ma)); } 11 }; 12 mat c; 13 char a[11]={}; 14 char b[4]={'A','G','C','T'}; 15 struct trie{ 16 int next[4]; 17 bool exist; 18 int fail; 19 int di;//缩小矩阵之后重定向 20 }e[110]; 21 int tot=0,tot1=0; 22 int point[110]={};//缩小矩阵用 23 int q[110]={};//队列 24 int w[110]={};//判定到此处是否为病毒 25 void Init(){ 26 int k=strlen(a),x=0; 27 for(int i=0;i<k;i++){ 28 int j; 29 for(j=0;j<=4;j++){ 30 if(b[j]==a[i]){ 31 break; 32 } 33 } 34 if(!e[x].next[j]){ 35 e[x].next[j]=++tot; 36 }x=e[x].next[j]; 37 } 38 e[x].exist=1; 39 } 40 void GetTri(){ 41 int head=0,tail=0,f,x,y; 42 q[0]=0; 43 while(head<=tail){ 44 x=q[head];head++; 45 for(int i=0;i<4;i++){ 46 if(e[x].next[i]){ 47 y=e[x].next[i]; 48 if(x!=0){ 49 f=e[x].fail; 50 while(f&&!e[f].next[i]){ 51 f=e[f].fail; 52 } 53 e[y].fail=e[f].next[i]; 54 w[y]=w[e[y].fail]; 55 } 56 if(e[y].exist){ 57 w[y]=1; 58 } 59 q[++tail]=y; 60 } 61 } 62 } 63 } 64 void MakMat(){ 65 int x,x1,y; 66 bool f; 67 for(int i=0;i<=tot;i++){ 68 x=point[i]; 69 for(int j=0;j<4;j++){ 70 f=1; 71 x1=x; 72 for(;;){ 73 if(e[x1].next[j]){ 74 f=0; 75 y=e[x1].next[j]; 76 if(!w[y]){ 77 c.ma[i][e[y].di]++; 78 } 79 break; 80 } 81 if(x1==0){ 82 break; 83 } 84 x1=e[x1].fail; 85 } 86 if(f){ 87 c.ma[i][0]++; 88 } 89 } 90 } 91 } 92 mat Mul(mat x,mat y){ 93 mat z; 94 for(int i=0;i<=tot;i++){ 95 for(int j=0;j<=tot;j++){ 96 for(int k=0;k<=tot;k++){ 97 z.ma[i][j]+=x.ma[i][k]*y.ma[k][j]; 98 z.ma[i][j]%=modn; 99 } 100 } 101 } 102 return z; 103 } 104 mat Pow(mat x,int k){ 105 mat z; 106 for(int i=0;i<=tot;i++){ 107 z.ma[i][i]=1; 108 } 109 while(k>0){ 110 if(k&1){ 111 z=Mul(z,x); 112 } 113 x=Mul(x,x); 114 k/=2; 115 } 116 return z; 117 } 118 int main(){ 119 memset(e,0,sizeof(e)); 120 scanf("%d%d",&m,&n); 121 for(int i=1;i<=m;i++){ 122 scanf("%s",&a); 123 Init(); 124 } 125 GetTri(); 126 tot1=tot;tot=0; 127 for(int i=1;i<=tot1;i++){ 128 if(!w[i]){ 129 point[++tot]=i; 130 e[i].di=tot; 131 } 132 } 133 MakMat(); 134 mat z=Pow(c,n); 135 long long ans=0; 136 /*for(int i=0;i<=tot;i++){ 137 for(int j=0;j<=tot;j++){ 138 std::cout<<c.ma[i][j]<<' '; 139 }std::cout<<std::endl; 140 }*/ 141 142 for(int i=0;i<=tot;i++){ 143 ans+=z.ma[0][i]; 144 ans%=modn; 145 } 146 printf("%lld ",ans); 147 return 0; 148 }