[2018HN省队集训D8T1] 杀毒软件
题意
给定一个 $m$ 个01串的字典以及一个长度为 $n$ 的 01? 序列. 对这个序列进行 $q$ 次操作, 修改某个位置的字符情况以及查询区间 $[l,r]$ 内的序列中有多少种在 ? 处填入 01 的方案可以让这个区间所代表的串不含有任何字典中的串作为子串.
方案 $\bmod 998244353$, $n,q \le 3\times 10^4, m\le 5$. 字典串总长不超过 $20$ 个字符.
题解
这是一道正解被暴力艹翻的题目
首先它要对一个东西进行多模式串匹配, 我们自然而然地想到一个东西叫AC自动机.
于是建一个AC自动机就可以直接对每次查询都 $O(nm)$ DP了($m$ 是AC自动机状态数). 然后再加个如果当前剩下的方案数为0即停止的优化就可以过了
注意到字典总长非常小, 我们完全可以把插入三种字符的转移过程分别写成矩阵. (注意需要把AC自动机展开成完整的DFA(或者称为Trie图)) 然后我们可以用线段树维护这个矩阵. 时间复杂度是 $O\left((n+q)(\sum p)^3\log n\right)$. 可以拿到TLE的好结果. (极限数据要 $20\texttt s+$你敢信?)
注意到矩阵中的转移极为稀疏, 加个当前位置是否为0的判断就可以40倍速AC了.
还有就是判断终止状态的时候要有后缀链接. 也就是说如果fail是终止状态那么当前也是终止状态. 考试的时候因为AC自动机是当场YY出来的于是没考虑这一步就GG了.
Orz swoky&hzoizcl
参考代码
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
|
#include <bits/stdc++.h>
const int MAXN=3e4+10;
const int MOD=998244353;
struct Matrix{
int n;
int m[20][20];
Matrix(int n):n(n){
memset(m,0,sizeof(m));
}
Matrix friend operator*(const Matrix& a,const Matrix& b){
int n=a.n;
Matrix ans(n);
for(int i=0;i<n;i++)
for(int k=0;k<n;k++)if(a.m[i][k])
for(int j=0;j<n;j++)if(b.m[k][j])
(ans.m[i][j]+=1ll*a.m[i][k]*b.m[k][j]%MOD)%=MOD;
return ans;
}
};
struct Node{
int l;
int r;
Matrix m;
Node* lch;
Node* rch;
Node(int,int);
void Modify(int,int);
Matrix Query(int,int);
};
int n;
int m;
int q;
int cnt;
int root;
int a[MAXN];
char s[MAXN];
int fail[MAXN];
bool end[MAXN];
int chd[MAXN][2];
void Insert(int,char*);
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=0;i<m;i++){
scanf("%s",s);
Insert(root,s);
}
{
std::queue<int> q;
for(int i=0;i<2;i++)
if(chd[0][i])
q.push(chd[0][i]);
while(!q.empty()){
int s=q.front();
q.pop();
for(int i=0;i<2;i++){
if(chd[s][i]==0)
chd[s][i]=chd[fail[s]][i];
else{
fail[chd[s][i]]=chd[fail[s]][i];
if(end[fail[chd[s][i]]])
end[chd[s][i]]=true;
q.push(chd[s][i]);
}
}
}
}
Node* N=new Node(1,n);
for(int i=0;i<q;i++){
scanf("%s",s);
if(*s=='C'){
int x,d;
scanf("%d%d",&x,&d);
N->Modify(x,d);
}
else{
int l,r;
scanf("%d%d",&l,&r);
Matrix m=N->Query(l,r);
int ans=0;
for(int i=0;i<=cnt;i++)
(ans+=m.m[0][i])%=MOD;
printf("%d\n",ans);
}
}
return 0;
}
void Insert(int cur,char* s){
if(*s=='\0')
end[cur]=true;
else{
int val=*s-'0';
if(!chd[cur][val])
chd[cur][val]=++cnt;
Insert(chd[cur][val],s+1);
}
}
Node::Node(int l,int r):l(l),r(r),m(cnt+1){
if(l==r){
for(int i=0;i<=cnt;i++){
if((a[l]==-1||a[r]==0)&&!end[chd[i][0]])
++m.m[i][chd[i][0]];
if((a[l]==-1||a[r]==1)&&!end[chd[i][1]])
++m.m[i][chd[i][1]];
}
}
else{
int mid=(l+r)>>1;
this->lch=new Node(l,mid);
this->rch=new Node(mid+1,r);
this->m=this->lch->m*this->rch->m;
}
}
void Node::Modify(int x,int d){
if(this->l==this->r){
memset(m.m,0,sizeof(m.m));
for(int i=0;i<=cnt;i++){
if((d==-1||d==0)&&!end[chd[i][0]])
++m.m[i][chd[i][0]];
if((d==-1||d==1)&&!end[chd[i][1]])
++m.m[i][chd[i][1]];
}
}
else{
if(x<=this->lch->r)
this->lch->Modify(x,d);
else
this->rch->Modify(x,d);
this->m=this->lch->m*this->rch->m;
}
}
Matrix Node::Query(int l,int r){
if(l<=this->l&&this->r<=r)
return this->m;
else{
if(r<=this->lch->r)
return this->lch->Query(l,r);
if(this->rch->l<=l)
return this->rch->Query(l,r);
return this->lch->Query(l,r)*this->rch->Query(l,r);
}
}
|
