题意:给定n个不能出现的模式串，给定一个长度m，要求长度为m的合法串有多少种。

思路：用AC自动机，利用AC自动机上的节点做矩阵乘法。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #define MOD 100000 9 char s[2005]; 10 int ch(char x){ 11 if (x=='A') return 0; 12 if (x=='C') return 1; 13 if (x=='G') return 2; 14 if (x=='T') return 3; 15 return -1; 16 } 17 struct Trie{ 18 int fail[1005],next[1005][5],end[1005],L,root; 19 int newnode(){ 20 for (int i=0;i<4;i++) 21 next[L][i]=-1; 22 end[L++]=-1; 23 return L-1; 24 } 25 void clear(){ 26 L=0; 27 root=newnode(); 28 } 29 void insert(char s[]){ 30 int len=strlen(s),now=root; 31 for (int i=0;i
            

Q; 39 int now; 40 for (int i=0;i<4;i++) 41 if (next[root][i]==-1) 42 next[root][i]=root; 43 else{ 44 fail[next[root][i]]=root; 45 Q.push(next[root][i]); 46 } 47 while (!Q.empty()){ 48 now=Q.front();Q.pop(); 49 if (end[fail[now]]==1) end[now]=1; 50 for (int i=0;i<4;i++){ 51 if (next[now][i]==-1) next[now][i]=next[fail[now]][i]; 52 else{ 53 fail[next[now][i]]=next[fail[now]][i]; 54 Q.push(next[now][i]); 55 } 56 } 57 } 58 } 59 }ac; 60 struct Matrix{ 61 int n,mx[105][105]; 62 Matrix(){} 63 Matrix(int x){ 64 n=x; 65 for (int i=0;i