POJ 2778 DNA sequence

QAQ 做完禁忌 又做过文本生成器 这道题就是个水题啦

首先转移方程还是文本生成器的转移方程

但是注意到L很大，但是节点数很小

转移都是固定的，所以我们可以用AC自动机来构造转移矩阵

之后进行矩阵乘法就可以了

顺便提一句，模数是10^5,相乘会爆int

我为了省点常数自信开int，结果WA了两发QAQ

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;

typedef long long LL;
const int maxn=112;
const int mod=100000;
int cnt=1;
int n,L,id[1010];
int t[maxn][4];
int fail[maxn];
char s[maxn];
bool end[maxn];
bool vis[maxn];
queue<int>Q;
struct Matrix{
	int a[maxn][maxn];
	Matrix(){memset(a,0,sizeof(a));}
	void print(){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				printf("%d ",a[i][j]);
			}printf("
");
		}printf("
");
	}
}A,ans;

void insert(){
	scanf("%s",s+1);
	int len=strlen(s+1),now=1;
	for(int i=1;i<=len;++i){
		int next=id[s[i]];
		if(!t[now][next])t[now][next]=++cnt;
		now=t[now][next];
	}end[now]=true;
}
void build_fail(){
	Q.push(1);fail[1]=0;
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		end[u]|=end[fail[u]];
		for(int i=0;i<4;++i){
			int k=fail[u];
			while(k&&!t[k][i])k=fail[k];
			if(t[u][i]){
				fail[t[u][i]]=k?t[k][i]:1;
				Q.push(t[u][i]);
			}else t[u][i]=k?t[k][i]:1;
		}
	}return;
}
void build_Matrix(){
	for(int i=1;i<=n;++i){
		if(end[i])continue;
		for(int j=0;j<4;++j){
			if(end[t[i][j]])continue;
			A.a[i][t[i][j]]++;
		}
	}return;
}
Matrix operator *(const Matrix &A,const Matrix &B){
	Matrix C;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			for(int k=1;k<=n;++k){
				C.a[i][j]=C.a[i][j]+1LL*A.a[i][k]*B.a[k][j]%mod;
				if(C.a[i][j]>=mod)C.a[i][j]-=mod;
			}
		}
	}
	return C;
}
Matrix pow_mod(Matrix v,int p){
	Matrix tmp;
	for(int i=1;i<=n;++i)tmp.a[i][i]=1;
	while(p){
		if(p&1)tmp=tmp*v;
		v=v*v;p>>=1;
	}return tmp;
}

int main(){
	scanf("%d%d",&n,&L);
	id['A']=0;id['T']=1;id['C']=2;id['G']=3;
	for(int i=1;i<=n;++i)insert();
	build_fail();n=cnt;
	build_Matrix();
	ans=pow_mod(A,L);
	int tot=0;
	for(int i=1;i<=n;++i){
		tot+=ans.a[1][i];
		if(tot>=mod)tot-=mod;
	}
	printf("%d
",tot);
	return 0;
}