POJ2778 (DNA Sequence)[AC自动机，图论，矩阵乘法]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=2778

题意：给定m个模板串，问有多少种长度为n的字符串使得它不包含任何一个模板串。

首先根据模板串建出trie图。可以想到任意一个字符串都对应了trie图上从根结点起始的一条路径。因此问题转化为在trie图中从根结点开始长度为n的，且不经过某些点的不同路径数量。

设A是图G的邻接矩阵，即：
$$
a_{ij}=
\begin{cases}
0& \text{节点i和节点j之间无边相连} \\
n& \text{节点i和节点j之间有边相连且边数为n}
\end{cases}
$$
注：除非有自环，否则$a_{ii}$为$0$
令$B=A^l$，则$b_{ij}$表示节点$i$到节点$j$长度为$l$的不同路径的数量。

将邻接矩阵中不能经过的节点（单词节点和能通过后缀链接到达单词节点的节点）对应的行列全部置为0,然后用矩阵快速幂算出结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long ll;
const int maxn=105;

int ch[maxn][4];
int f[maxn];
bool danger[maxn];
int sz;
void init (){
	sz=1;
	memset(ch[0],0,sizeof(ch[0]));
	memset(f,0,sizeof(f));
	memset(danger,0,sizeof(danger));
}
int idx(char c) { 
	if(c=='A') return 0;
	if(c=='C') return 1;
	if(c=='T') return 2;
	if(c=='G') return 3;
	return -1;
}
void insert(char *s) {
	int u=0,n=strlen(s);
	for(int i=0;i<n;i++) {
		int c=idx(s[i]);
		if(!ch[u][c]) {
			memset(ch[sz],0,sizeof(ch[sz]));
			danger[sz]=false;
			ch[u][c]=sz++;
		}
		u=ch[u][c];
	}
	danger[u]=true;
}
void getFail() {
	queue<int> q;
	while(!q.empty()) q.pop();
	f[0]=0;
	for(int c=0;c<4;c++) {
		int u=ch[0][c];
		if(u) { f[u]=0;q.push(u); }
	}
	while(!q.empty()) {
		int r=q.front(); q.pop();
		for(int c=0;c<4;c++) {
			int u=ch[r][c];
			if(!u) { ch[r][c]=ch[f[r]][c];continue; }
			q.push(u);
			int v=f[r];
			while(v && !ch[v][c]) v=f[v];
			f[u]=ch[v][c];
			danger[u]|=danger[ch[v][c]];
		}
	}
}

ll mat[maxn][maxn];
bool vis[maxn];
void build() {
	memset(mat,0,sizeof(mat));
	/*
	memset(vis,false,sizeof(vis));
	queue<int> q;
	while(!q.empty()) q.pop();
	vis[0]=true;
	for(int c=0;c<4;c++) {
		int u=ch[0][c];
		if(!danger[u]) { mat[0][u]=1;vis[u]=true;q.push(u); }
	}
	while(!q.empty()) {
		int r=q.front(); q.pop();
		for(int c=0;c<4;c++) {
			int u=ch[r][c];
			if(danger[u]) continue;
			mat[r][u]=1;
			if(!vis[u]) { vis[u]=true;q.push(u); }
		}
	}
	*/
	for(int i=0;i<sz;i++) if(!danger[i]) {
		for(int j=0;j<4;j++) {
			int u=ch[i][j];
			if(!danger[u]) mat[i][u]++;
		}
	}
}

ll ans[maxn][maxn];
void pow_mod(int y,int M) {
	ll tmp[maxn][maxn];
	for(int i=0;i<sz;i++)
		ans[i][i]=1;
	for(;y;y>>=1) {
		if(y&1) {
			memset(tmp,0,sizeof(tmp));
			for(int i=0;i<sz;i++)
				for(int j=0;j<sz;j++)
					for(int k=0;k<sz;k++) 
						tmp[i][j]=((ans[i][k]*mat[k][j])%M+tmp[i][j])%M;
			memcpy(ans,tmp,sizeof(tmp));
		}
		memset(tmp,0,sizeof(tmp));
		for(int i=0;i<sz;i++)
			for(int j=0;j<sz;j++)
				for(int k=0;k<sz;k++) 
					tmp[i][j]=((mat[i][k]*mat[k][j])%M+tmp[i][j])%M;
		memcpy(mat,tmp,sizeof(tmp));
	}
}

char s[15];
int main() {
    int n,m;
	scanf("%d%d",&m,&n);
	init();
	for(int i=0;i<m;i++) {
		scanf("%s",s);
		insert(s);
	}
	getFail();
	build();
	pow_mod(n,100000);
	int a=0;
	for(int i=0;i<sz;i++) {
		a=(ans[0][i]+a)%100000;
	}
	printf("%d",a);
}