题意：给你n个DNA序列然后求有多少个m长度的DNA序列不含有这个n个DNA序列的任意一个
题解思路：那么这和矩阵有什么关系呢？我假设当前状态处于某个DNA序列的第a点
那么我下一步可以走的就是下一个点不是任何DNA序列的尾结点然后把这个图看成一个有向图
那么就是变成求长度为n的路径有几条最终的答案就是从结点0走到结点{0,1,2,3,。。。。。sz-1}此时的sz就是结点个数，然后用字典树加AC自动机构造出一个有向图然后用这个有向图构造出一个矩阵
#include<iostream> #include<cstring> #include<queue> #include<algorithm> #include<cstdio> using namespace std; const int mx = 1005; typedef long long int ll; const ll p = 100000; struct mat{ ll a[105][105]; }; struct trie{ int ch[mx][4]; int f[mx]; int v[mx]; int sz; mat x; void init(){ memset(ch[0],0,sizeof(ch[0])); memset(f,0,sizeof(f)); memset(v,0,sizeof(v)); sz = 1; } int idx(char c){ if(c == 'A') return 0; else if(c == 'C') return 1; else if(c == 'T') return 2; else return 3; } void insert(char *s){ int len = strlen(s); int u = 0; for(int i = 0; i < len; i++){ int d = idx(s[i]); if(!ch[u][d]){ memset(ch[sz],0,sizeof(ch[sz])); ch[u][d] = sz++; } u = ch[u][d]; } v[u] = 1; } void getfail(){ queue<int>q; for(int d = 0; d < 4; d++){ if(!ch[0][d]){ ch[0][d] = 0; continue; } f[ch[0][d]] = 0; q.push(ch[0][d]); } while(!q.empty()){ int u = q.front(); q.pop(); if(v[f[u]]) //这个点能匹配到其他DNA序列的尾巴结点那么这个点也不行 v[u] = 1; for(int d = 0; d < 4; d++){ if(!ch[u][d]){ ch[u][d] = ch[f[u]][d]; continue; } f[ch[u][d]] = ch[f[u]][d]; q.push(ch[u][d]); } } } void getmat(){ for(int i = 0; i < sz; i++) for(int j = 0; j < sz; j++) x.a[i][j] = 0; for(int i = 0; i < sz; i++) for(int j = 0; j < 4; j++) if(!v[i]&&!v[ch[i][j]]) //要这个点不是尾结点下一个点也不是尾结点的才可以 x.a[i][ch[i][j]]++; } mat calc(mat x,mat y){ mat z; for(int i = 0; i < sz; i++) for(int j = 0; j < sz; j++){ z.a[i][j] = 0; for(int k = 0; k < sz; k++) z.a[i][j] += x.a[i][k]*y.a[k][j]; z.a[i][j] = z.a[i][j]%p; } return z; } ll getans(int n){ mat cnt = x; while(n){ if(n&1) cnt = calc(cnt,x); x = calc(x,x); n /= 2; } ll ans = 0; for(int i = 0; i < sz; i++) ans = (ans + cnt.a[0][i])%p; return ans; } }word; char s[mx]; int n,m; int main(){ while(~scanf("%d%d",&n,&m)){ word.init(); for(int i = 0; i < n; i++){ scanf("%s",s); word.insert(s); } word.getfail(); word.getmat(); printf("%lld\n",word.getans(m-1)%p); } return 0; }