链接
http://poj.org/problem?id=2778
题意
字符集为 A，C，T，G，有 $m$ $(m\le10)$ 个长度小于等于 $10$ 的模式串，求长度为 $n$ 且不包含这些模式串的字符串个数。
思路
建立 AC 自动机，判断每个节点的后缀是否是模式串。
记 $dp_{i,j}$ 为在 Trie 上从根节点出发走了 $i$ 步到达节点 $j$ 且没有经过模式串的方案数，等价于长度为 $i$ 以节点 $j$ 代表的字符串为后缀且没有经过模式串的字符串个数。
记 $a_{i,j}$ 为从 Trie 上节点 $i$ 走一步到达节点 $j$ 的方案数，Trie 除根节点外有 $k$ 个节点：
$\begin{aligned}
& dp_{i,j}=dp_{i-1,0}*a_{0,j}+dp_{i-1,1}*a_{1,j}+\cdots+dp_{i-1,k}a_{k,j} \
\Longrightarrow & \begin{bmatrix}
dp_{i,0} & dp_{i,1} & \cdots & dp_{i,k}
\end{bmatrix}=
\begin{bmatrix}
dp_{i-1,0} & dp_{i-1,1} & \cdots & dp_{i-1,k} \
\end{bmatrix}
\begin{bmatrix}
a_{0,0} & a_{0,1} & \cdots & a_{0,k} \
a_{1,0} & a_{1,1} & \cdots & a_{1,k} \
\vdots & \vdots & \ddots & \vdots \
a_{k,0} & a_{k,1} & \cdots & a_{k,k} \
\end{bmatrix}
\end{aligned}$
$\begin{bmatrix}
dp_{i,0} & dp_{i,1} & \cdots & dp_{i,k}
\end{bmatrix}$ 为 $\begin{bmatrix}
a_{0,0} & a_{0,1} & \cdots & a_{0,k} \
a_{1,0} & a_{1,1} & \cdots & a_{1,k} \
\vdots & \vdots & \ddots & \vdots \
a_{k,0} & a_{k,1} & \cdots & a_{k,k} \
\end{bmatrix}^{i}$ 的第一行。
最终答案为 $\sum_{i=0}^kdp_{n,i}$。
代码
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
| #include <iostream>
#include <cstring>
#include <queue>
#define SZ(x) (int)(x).size()
using namespace std;
typedef long long LL;
const LL MOD=100000;
const int N=15;
int n,m,tr[N*N][4],fail[N*N],st[N*N],cnt;
struct M {
LL a[N*N][N*N];
void clear() {memset(a,0,sizeof a);}
M() {clear();}
M operator * (const M &T) const {
M ret;
for(int i=0;i<=cnt;i++)
for(int k=0;k<=cnt;k++) {
LL t=a[i][k];
if(!t) continue;
for(int j=0;j<=cnt;j++) {
if(!T.a[k][j]) continue;
ret.a[i][j]=(ret.a[i][j]+T.a[k][j]*t%MOD)%MOD;
}
}
return ret;
}
M operator ^ (LL b) const {
M ret,bas;
for(int i=0;i<=cnt;i++) ret.a[i][i]=1;
for(int i=0;i<=cnt;i++)
for(int j=0;j<=cnt;j++)
bas.a[i][j]=a[i][j];
while(b) {
if(b&1) ret=ret*bas;
bas=bas*bas;
b>>=1;
}
return ret;
}
}mat;
int get(char c) {
if(c=='A') return 0;
if(c=='C') return 1;
if(c=='T') return 2;
return 3;
}
void insert(const string &s) {
int u=0;
for(int i=0;s[i];i++) {
int v=get(s[i]);
if(!tr[u][v]) tr[u][v]=++cnt;
u=tr[u][v];
}
st[u]=1;
}
void build() {
queue<int> q;
for(int i=0;i<4;i++) if(tr[0][i]) q.push(tr[0][i]);
while(SZ(q)) {
int u=q.front();
q.pop();
for(int v=0;v<4;v++) {
if(tr[u][v]) fail[tr[u][v]]=tr[fail[u]][v],q.push(tr[u][v]);
else tr[u][v]=tr[fail[u]][v];
}
st[u]|=st[fail[u]];
}
}
void get_matrix() {
for(int i=0;i<=cnt;i++) {
if(st[i]) continue;
for(int j=0;j<4;j++) {
if(st[tr[i][j]]) continue;
++mat.a[i][tr[i][j]];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++) {
string s;
cin>>s;
insert(s);
}
build();
get_matrix();
mat=mat^n;
LL res=0;
for(int i=0;i<=cnt;i++) res=(res+mat.a[0][i])%MOD;
cout<<res<<'\n';
return 0;
}
|