这道题极好的展示了AC自动机在构造转移图DFA上的应用
DFA转移图就是展示状态的转移过程的图，DFA图构造出来后就可以用DP求出任何DNA长度下，任何状态的个数
本题用自动机求出DFA矩阵，那么有
| dp[n][0] dp[n][1] … dp[n][m] |=|dp[1][0] dp[1][1] … dp[1][m] | * DFA^(n-1) (m指状态总数)
DP边界矩阵|dp[1][0] dp[1][1] … dp[1][m] | 也就是DFA的第一行，所以dp[n]矩阵就是DFA^n
可见用自动机求某类状态转移方程不仅思路简单，而且可以用矩阵快速幂加速状态转移，，复杂度log N
我是通过这篇学会的，感谢
//Accepted796K360MSC++3171B#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const int M = 110;const int mod = 100000;struct mat{ll a[M][M];mat(){memset(a,0,sizeof(a));}};mat DFA;struct node{node *son[4];node *fail;bool flag;int id;}trie[M],*que[M],*root;int Index(char x){switch(x){case 'A' : return 0;case 'C' : return 1;case 'G' : return 2;case 'T' : return 3;}}struct AC{int head,tail,sz;node *createnode(){trie[sz].flag=0;memset(trie[sz].son,0,sizeof(trie[sz].son));trie[sz].fail=NULL;trie[sz].id=sz;return &trie[sz++];}void ini(){head=tail=0;sz=0;root=createnode();}void Insert(char str[]){node *cur=root;for(int i=0;str[i];i++){int val=Index(str[i]);if(cur->flag) break;// 如果当前插入的已经是危险片段那么就可以不用继续插入了（针对此题而言）//要继续插入也可以不过它的后面全要标记成危险片段if(cur->flag) cur->son[val]->flag=true;if(cur->son[val]==NULL){cur->son[val]=createnode();}cur=cur->son[val];}cur->flag=true;}void acfun(){que[head++]=root;while(tail<head){node *cur=que[tail++];for(int i=0;i<4;i++){if(cur->son[i]!=NULL){if(cur==root) cur->son[i]->fail=root;else cur->son[i]->fail=cur->fail->son[i];if(cur->son[i]->fail->flag) cur->son[i]->flag=true; //易遗漏que[head++]=cur->son[i];}else{if(cur==root) cur->son[i]=root;else cur->son[i]=cur->fail->son[i];}}}}}ac;mat mul(mat m1,mat m2){mat ans;for(int i=0;i<ac.sz;i++)for(int j=0;j<ac.sz;j++)if(m1.a[i][j])for(int k=0;k<ac.sz;k++){ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%mod;}return ans;}int quickmul(mat m,int n){mat ans;for(int i=0;i<ac.sz;i++) ans.a[i][i]=1;while(n){if(n&1) ans=mul(ans,m);m=mul(m,m);n>>=1;}ll sum=0;for(int i=0;i<ac.sz;i++){sum+=ans.a[0][i];}return sum%mod;}void ini(){ac.ini();memset(DFA.a,0,sizeof(DFA.a));}int main(){int m,n;while(~scanf("%d%d",&m,&n)){ini();while(m–){char tmp[15];scanf("%s",tmp);ac.Insert(tmp);}ac.acfun();for(int i=0;i<ac.sz;i++){if(!trie[i].flag){for(int j=0;j<4;j++){if(!trie[i].son[j]->flag)DFA.a[i][trie[i].son[j]->id ]++;}}}printf("%d\n",quickmul(DFA,n));}}
偶尔会想，如果人生真如一场电子游戏，
