标签: matrix - CheaSim Blog

DNA Sequence

DNA Sequence

题意

给定$m$个指定串,寻找长度为$n$的不含指定串的字符串。

题解

AC自动机+dp+矩阵快速幂。

如果要不含病毒串,那么我们相当于在每个状态中不能指向那个病毒终点串。对于每个状态来说,可以选择的就是4个字母去掉下一个状态是病毒的字母。

$dp[i] += dp[j] (j是非病毒终点)$

初始化$dp[i]$为可以选择的字母。相当于$i$状态加上状态$j$乘上字母数。可以构造一个矩阵mx。$mx[i][j]$表示$i$到$j$的字母数,矩阵的$n$次方之后就是经过$n$个状态转化后的值。

举个例子,比如我们是AC,AT,AG,AA这四个病毒串,那么root = 0,A是1,C=2,T=3,A=4。有五个状态。

当我们状态为0的时候,有两种选择。我们到状态0的选择字母可以选3个’C’’T’’G’。到状态1可以选1个’A’。之后到状态1没有选择了,因为全是病毒串。所以我们的矩阵是

3 1

0 0

之后矩阵乘就完事了。

我感觉讲得有点不清楚。。。

+2 TLE因为矩阵的大小是有build的trie树决定的,所以越小越好用ac.tot来表示矩阵的大小,也就是状态的大小。

+10 矩阵的大小其实是状态的大小,状态的大小是 输入的病毒串长度*病毒串的次数。最大tot为这么大。

+1 因为转移的状态只有四种,所以maxson为4就好了,大了的话创造矩阵的时候会出现问题。

###ac代码

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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxson = 4;
const ll mod = 100000;
int n,m;
const int MAX = 110;
int tot = 0;
struct Matrix{
ll mx[MAX][MAX];
int n;
Matrix(){memset(mx,0,sizeof(mx)); n = MAX;}
Matrix operator +(const Matrix &b)const{
Matrix res;
rep(i,0,MAX) rep(j,0,MAX)
res.mx[i][j] = (mx[i][j]+b.mx[i][j])%mod;
return res;
}
Matrix operator *(const Matrix &b) const{
Matrix res;
rep(i,0,tot) rep(j,0,tot) {
rep(k,0,tot){
res.mx[i][j] += mx[i][k]*b.mx[k][j];
}
res.mx[i][j] %= mod;
}
return res;
}
void debug(){
rep(i,0,n){
rep(j,0,n){
cout<<mx[i][j]<<' ';
}
cout<<endl;
}
}
}U,V;
Matrix pow3(Matrix f,int n){
Matrix res;
rep(i,0,MAX) res.mx[i][i] = 1;
while(n){
if(n&1) res = res*f;
n>>=1;
f = f*f;
}
return res;
}
struct Trie{
int next[20*20][maxson],fail[20*20],flag[20*20];
int root,tot;
int encode[256];
int newnode(){
rep(i,0,maxson) next[tot][i] = -1;
flag[tot++] = 0;
return tot-1;
}
void init(){
tot = 0;
root = newnode();
encode['A'] = 0;
encode['T'] = 1;
encode['C'] = 2;
encode['G'] = 3;
memset(flag,0,sizeof(flag));
}
void insert(char *s,int id){
int len = strlen(s);
int now = root;
rep(i,0,len){
int k = encode[s[i]];
if(next[now][k] == -1)
next[now][k] = newnode();
now = next[now][k];
}
flag[now] = id;
}
void build(){
queue<int> q;
fail[root] = root;
rep(i,0,maxson){
if(next[root][i] == -1){
next[root][i] = root;
}else{
fail[next[root][i]] = root;
q.push(next[root][i]);
}
}
while(!q.empty()){
int now = q.front(); q.pop();
if(flag[fail[now]]) flag[now] = 1;
rep(i,0,maxson){
if(next[now][i] == -1){
next[now][i] = next[fail[now]][i];
}else{
fail[next[now][i]] = next[fail[now]][i];
q.push(next[now][i]);
}
}
}
}
Matrix build_mx(){
Matrix res;
rep(i,0,tot) rep(j,0,maxson){
if(flag[i] != 1 && flag[next[i][j]] != 1 ){
res.mx[i][next[i][j]] ++;
}
}
return res;
}
void debug(){
for (int i = 0; i < tot; i++){
printf("id = %3d,fail = %3d,end = %3d,chi = [", i, fail[i], flag[i]);
for (int j = 0; j < maxson; j++) printf("%2d", next[i][j]);
printf("]\n");
}
}
}ac;
char s[30];
int main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
#endif // LOCAL
scanf("%d%d",&n,&m);
ac.init();
rep(i,0,n){
scanf("%s",s);
ac.insert(s,1);
}
ac.build();
tot = ac.tot;
Matrix res1 = ac.build_mx();
Matrix res = pow3(res1,m);
ll ans = 0;
res1.debug();
rep(i,0,ac.tot){
ans += res.mx[0][i];
}
ans = ans % mod;
printf("%d\n",ans);

return 0;
}