poj-2778 DNA Sequence

题意：

给出n个AGCT组成的字符串和一个数m；

求AGCT能组成的长度为m的串的个数；

n<=10，字符串长度<=10，m<=2x10^9；

题解：

构造一个满足题意的长度为x的串之前，我们要先构筑出一个长度为x-1的串；

显然倘若要让x的符合题意，x-1的必符合题意；

那么既然串的前半部分都已经符合题意了，我们只需要考虑x-1那个串的后缀；

就是说那个后缀再加上一个字符之后，能否满足题意；

而当构造x+1的串时，x的后缀成为新的要考虑的状态；

那么就可以说，x-1的后缀状态是与x的状态有连边的，x与x+1的也是；

那么我们倘若构造出了对于所有的x之间的连边关系的图，以其为邻接矩阵做矩阵乘法就可以了；

实际上，因为能否成功构成下一个串只与后缀有关，而阻止构成的字符串只有10个，长度为10；

所以需要讨论的状态最多有100种；

那么处理矩阵就用ac自动机，字典树上的每个点都可以代表一个后缀；

在后缀后面加上字符，可能将他向下拓展，或者因为匹配不能而跳转到fail指针下的next[i]处；

然后有病毒的地方是不能连边的，有病毒作为子串的后缀也是如此；

时间复杂度大概是O(n^2+100^3lgm)的样子；

数组版的AC自动机不太习惯，写的较丑勿怪；

代码：

#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 101
#define mod 100000
using namespace std;
typedef long long ll;
struct trie
{
	int fail,next[4];
	bool is;
}tr[N];
struct matrix
{
	ll a[N][N];
}In,T,ans;
queue<int>q;
char str[20];
int tot;
int in(char ch)
{
	switch(ch)
	{
		case'A':return 0;
		case'G':return 1;
		case'C':return 2;
		case'T':return 3;
	};
}
matrix mul(matrix x,matrix y)
{
	matrix ret;
	int i,j,k;
	for(i=1;i<=tot;i++)
		for(j=1;j<=tot;j++)
			for(k=1,ret.a[i][j]=0;k<=tot;k++)
				ret.a[i][j]=(ret.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
	return ret;
}
matrix pow(matrix x,ll y)
{
	matrix ret=In;
	while(y)
	{
		if(y&1)
			ret=mul(ret,x);
		x=mul(x,x);
		y>>=1;
	}
	return ret;
}
void insert(int root,char *s)
{
	int index,p=root;
	while(*s!='\0')
	{
		index=in(*s);
		if(tr[p].next[index]==0)
			tr[p].next[index]=++tot;
		p=tr[p].next[index];
		s++;
	}
	tr[p].is=1;
}
void build(int root)
{
	q.push(root);
	while(!q.empty())
	{
		int p=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			if(tr[p].next[i])
			{
				if(p==root)	tr[tr[p].next[i]].fail=root;
				else
				{
					int temp=tr[p].fail;
					while(temp)
					{
						if(tr[temp].next[i])
						{
							tr[tr[p].next[i]].fail=tr[temp].next[i];
							tr[tr[p].next[i]].is|=tr[tr[temp].next[i]].is;
							break;
						}
						temp=tr[temp].fail;
					}	
					if(temp==0)	tr[tr[p].next[i]].fail=root;
				}
				q.push(tr[p].next[i]);
			}
			else
			{
				if(p==root)
					tr[p].next[i]=root;
				else
					tr[p].next[i]=tr[tr[p].fail].next[i];
			}
		}
	}
}
void initmat(int root)
{
	int i,j,k;
	for(i=1;i<=tot;i++)
	{
		if(tr[i].is)			continue;
		for(k=0;k<4;k++)
		{
			if(tr[j=tr[i].next[k]].is)	continue;
			T.a[i][j]++;
		}
	}
	for(i=1;i<=tot;i++)
			In.a[i][i]=1;
}
int main()
{
	int n,i,j,k;
	ll m,sum;
	scanf("%d%lld",&n,&m);
	for(i=1,tot=1;i<=n;i++)
	{
		scanf("%s",str);
		insert(1,str);
	}
	build(1);
	initmat(1);
	ans=pow(T,m);
	for(i=1,sum=0;i<=tot;i++)
		sum=(sum+ans.a[1][i])%mod;
	printf("%lld",sum);
	return 0;
}