zoj2778——trie图+矩阵快速幂

好题,trie图建好后,写出它的邻接矩阵形式,m[i][j]表示从结点i经过一步到达j的方法数(边数).注意,不能经过危险结点(何为危险结点?请参考wc的论文《trie树的改进与活用》),所以到达从点i到达危险结点的方法数设为0.这样最后结果才表示走n步(相当于写了n个字母)后没有包含单词结点的字符串数量。
注意:这里补全了结点的所有’A'——’Z'的孩子,但实际只可能转向’A'、’C'、’G'、T’,所以其他虚拟孩子不用考虑。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
#define maxn 110
#define CH 27
int chd[maxn][CH];
int fail[maxn],val[maxn];
int sz;
typedef struct Mat{
	__int64 m[maxn][maxn];
}Mat;
Mat per;
Mat multi(Mat a,Mat b)
{
	Mat ans;
	int i,j,k;
	for(i=0;i<=sz-1;i++)
		for(j=0;j<=sz-1;j++)
		{
			__int64 tmp=0;
			for(k=0;k<=sz-1;k++)
				tmp+=a.m[i][k]*b.m[k][j];
			tmp=tmp%100000;
			ans.m[i][j]=tmp;
		}
	return ans;
}
Mat power(Mat a,int k)
{
	Mat p=a,ans=per;
	while(k)
	{
		if(k&1)
		{
			k--;
			ans=multi(ans,p);
		}
		else
		{
			k/=2;
			p=multi(p,p);
		
		}
	}
	return ans;
}
void init(){
    memset(chd[0],0,sizeof(chd[0]));
    sz=1;
    val[0]=0;
}
void insert(char s[]){
    int i=0,p=0;
	int len=strlen(s);
    for(i=0;i<=len-1;i++)
	{
        int x=s[i]-'A'+1;
        if(!chd[p][x]){
            memset(chd[sz],0,sizeof(chd[sz]));
            val[sz]=0;
            chd[p][x]=sz++;
        }
        p=chd[p][x];
    }
    val[p]=1;
}
void build_fail()
{
    queue<int> que;
    for(int i=1;i<=CH-1;i++)
		if(chd[0][i])
		{
			fail[chd[0][i]]=0;
			que.push(chd[0][i]);
		}
    while(!que.empty())
	{
        int p=que.front();
        que.pop();
        for(int i=1;i<=CH-1;i++)
		{
            if(chd[p][i])
			{
                int v=chd[p][i];
                que.push(v);
                fail[v]=chd[fail[p]][i];
				val[v]=val[v]|val[fail[v]];
                
            }
			else
			{
                chd[p][i]=chd[fail[p]][i];
            }
        }
    }
}
int main()
{
	int m,n;
	int i,j;
	while(scanf("%d %d",&m,&n)!=EOF)
	{
		getchar();
		for(i=0;i<=100;i++)
			for(j=0;j<=100;j++)
			{
				per.m[i][j]=(i==j);
			}
		init();
		char s[15];
		for(i=1;i<=m;i++)
		{
			gets(s);
			insert(s);
		}
		build_fail();
		Mat opt;
		for(i=0;i<=100;i++)
			for(j=0;j<=100;j++)
				opt.m[i][j]=0;
		int a[5];
		a[1]='A'-'A'+1;a[2]='C'-'A'+1;a[3]='G'-'A'+1;a[4]='T'-'A'+1;
		for(i=0;i<=sz-1;i++)
		{
			for(j=1;j<=4;j++)
			{
				if(val[chd[i][a[j]]]!=1)
					opt.m[i][chd[i][a[j]]]=(opt.m[i][chd[i][a[j]]]+1)%100000;
			
			}
		}
		Mat tmp=power(opt,n);
		__int64 ans=0;
		for(i=0;i<=sz-1;i++)
			ans=(ans+tmp.m[0][i])%100000;//连走到危险结点也加进去了?非也,tmp.m[0][危险结点]必然是0。(思考:为什么)
		printf("%I64d\n",ans);
	}
    return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>