[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

參考代碼

#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);elsethis->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);} }

轉載于:https://www.cnblogs.com/rvalue/p/10505363.html

總結

以上是生活随笔為你收集整理的[2018HN省队集训D8T1] 杀毒软件的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。