【POJ 2778】DNA Sequence

题目传送门：http://poj.org/problem?id=2778
数据生成器：http://paste.ubuntu.com/17964294/

说好久没写AC自动机+矩阵快速幂了，专门找了一道来练练手
果然wa了好久好久，不过欣慰的是AC自动机还勉强能写出来

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const LL MOD = 100000;
const int MAXN = 100+9;
const int SIGMA_SIZE = 4;

char pat[MAXN];
int N,m,lim,vout;

struct Matrix{
	LL a[109][109];
	
	Matrix(){}
	Matrix(int val){
		for (int i=1;i<=lim;i++)
			memset(a[i],0,sizeof(a[i]));
		for (int i=1;i<=lim;i++)
			a[i][i] = val;
	}
	
}A(0);

inline void Mul(Matrix &M1, Matrix &M2){
	 Matrix ret(0);
	 for (int i=1;i<=lim;i++)
	 	for (int j=1;j<=lim;j++)
	 		for (int k=1;k<=lim;k++) ret.a[i][j] = (ret.a[i][j]+M1.a[k][j]*M2.a[i][k])%MOD; M1 = ret; } inline void Matrix_pow(Matrix &M, int t){ Matrix tmp(1); while (t) { if (t & 1) Mul(tmp, M); Mul(M,M); t >>= 1;
	}
	M = tmp;
}

namespace AC_Automaton{
	#define AC AC_Automaton
	int ch[MAXN][SIGMA_SIZE],get[MAXN];
	int fail[MAXN],cnt=1;
	int que[MAXN],frt,bak;
	
	inline int ord(char c){
		if (c=='A') return 0;
		else if (c=='T') return 1;
		else if (c=='C') return 2;
		else return 3;
	}
	
	inline void insert(char *s){
		int n = strlen(s+1), w = 1;
		for (int i=1,c;i<=n;i++){
			c = ord(s[i]);
			if (!ch[w]) ch[w] = ++cnt;
			w = ch[w];
		}
		get[w]=1;
	}
	
	inline void GetFail(){
		fail[1] = 1; bak=1; lim = cnt; 
		for (int i=0;i<SIGMA_SIZE;i++) if (ch[1][i]) que[++frt]=ch[1][i], fail[ch[1][i]]=1; while (frt >= bak){
			int w = que[bak++]; if (get[fail[w]]) get[w]=1;
			for (int c=0;c<SIGMA_SIZE;c++)if(ch[w]){ int nw = fail[w]; if (get[w]) get[ch[w]] = 1; while (!ch[nw] && nw>1) nw = fail[nw];
				if (!ch[nw]) fail[ch[w]] = nw;
				else fail[ch[w]] = ch[nw];
				que[++frt] = ch[w]; 
			}
		}
	}
	
	inline void Build_Matrix(){
		que[frt=1]=1; bak=1;
		while (frt >= bak){
			int w = que[bak++];
			for (int c=0;c<SIGMA_SIZE;c++)if(ch[w]){ if (!get[ch[w]]) A.a[ch[w]][w]++, que[++frt] = ch[w]; } else { int nw = fail[w]; while (!ch[nw] && nw>1) nw=fail[nw];
				if (ch[nw]) nw = ch[nw]; 
				if (!get[nw]) A.a[nw][w]++;	
			}
		}
	}
};

int main(){
	scanf("%d%d",&N,&m);
	for (int i=1;i<=N;i++){
		scanf("%s",pat+1);
		AC::insert(pat);
	} 
	AC::GetFail();
	AC::Build_Matrix();
	
	Matrix_pow(A,m); 
	for (int i=1;i<=lim;i++)
		vout = (vout+A.a[i][1])%MOD;
	printf("%d\n",vout);
	
	return 0;
}