#include<stdio.h>
struct node
{
	struct node *next[5];
	struct node *fail;
	int flag,num;
}*root,*line[3000];
int m,n,i,j,nu,head,tail,key,k;
long long anss;
char str[20];
struct M
{
	long long x[300][300];
}*mat,*ans;
int getnum(char c)
{
	if (c=='A') return 1;
	if (c=='C') return 2;
	if (c=='G') return 3;
	if (c=='T') return 4;
}
void trie()
{
	struct node *p=root;
	int i=1;  int key;
	while (i<=strlen(str))
	{
		key=getnum(str[i-1]);
		if (p->next[key]==NULL)
		{
			p->next[key]=(struct node *)malloc(sizeof(struct node));
			nu++;
			p->next[key]->num=nu;
			for (j=1;j<=4;j++)
			{
				p->next[key]->next[j]=NULL;
			}
			p->next[key]->flag=0;
		}
		p=p->next[key];
		i++;
	}
	p->flag=1;
}
void buildac()
{
	root->fail=NULL;
	line[1]=root;
	head=0; tail=1;
	while (head<tail)
	{
        head++;
		struct node *p=line[head];
		for (i=1;i<=4;i++)
		{
			if (p->next[i]!=NULL)
			{
				if (p==root) p->next[i]->fail=root;
				else 
				{
					struct node *temp=p->fail;
					while (temp!=NULL)
					{
						if (temp->next[i]!=NULL) 
						{
							p->next[i]->fail=temp->next[i];
							break;
						}
						temp=temp->fail;
					}
					if (temp==NULL) p->next[i]->fail=root;
				}
				tail++;
				line[tail]=p->next[i];
			}
		}
	}
}
void buildmat()
{
	struct node *p=root;
	line[head]=root;
	head=0;tail=1;
	int i;
	while (head<tail)
	{
		head++;
		p=line[head];
		if (p!=NULL && p->flag==0)
		{
			key=p->num;
			for (i=1;i<=4;i++)
			{
				if (p->next[i]!=NULL && p->next[i]->flag==0)
					mat->x[key][p->next[i]->num]++;
				if (p->next[i]==NULL) mat->x[key][1]++;
				if (p->next[i]!=NULL)
				{
                                     tail++;
                                     line[tail]=p->next[i];
                }
			}
		}
	}
}
struct M *mul(struct M *a, struct M *b)
{
	struct M *c;
	c=(struct M *)malloc(sizeof(struct M));
	for (i=1;i<=nu;i++)
	{
		for (j=1;j<=nu;j++)
		{
			c->x[i][j]=0;
			for (k=1;k<=nu;k++)
			{
				c->x[i][j]+=(a->x[i][k])*(b->x[k][j]);
			}
		}
	}
	return c;
}
struct M *mi(struct M *a,int n)
{
	struct M *ans;
	ans=(struct M *)malloc(sizeof(struct M));
	for (i=1;i<=nu;i++)
		ans->x[i][i]=1;
	while (n)
	{
		if (n&1) ans=mul(a,ans);
		a=mul(a,a);
		n=n>>1;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&m,&n);
	root=(struct node *)malloc(sizeof(struct node));
	for (i=1;i<=4;i++)
	{
		root->next[i]=NULL;
	}
	root->flag=0;
	root->num=1;
	nu=1;
	for (i=1;i<=m;i++)
	{
		scanf("%s",str);
		trie();
	}
	buildac();
	mat=(struct M *)malloc(sizeof(struct M));
	buildmat();
	mat=mi(mat,n);
	for (i=1;i<=nu;i++)
	{
		anss+=mat->x[1][i];
	}
	printf("%lld\n",(anss%100000));
//	system("pause");
	return 0;
}

• 用C++交交看 (3136) yygy 2014-06-29 08:30:19