「Wdsr-3」蓬萊藥局 題解
綜合性比較強的 AC 自動機題目，我們可以對這道題逐步分解求解。
\(\rm subtask\ 1\)
沒有變換，問題轉化成多模式串單文本串，求文本串的每個前綴的模式串出現次數，AC 自動機模板題，也可以用後綴數據結構解決，這裡不多做解釋，可以出門左轉你谷模板區自行學習（AC 自動機模板都不會就來刷字元串黑題？），時間複雜度就是 AC 自動機模板的時間複雜度 \(\mathcal O\left(n+|\Sigma|\sum|g_i|\right)\)。
\(\rm subtask\ 2\)
直接暴力，對正解沒什麼啟示，這裡直接 skip。
\(\rm subtask\ 3\)
這檔部分分的特點是只經過一個時刻，只有一個模式串，且串里只有 \(1\)，那麼我們可以運用 dp 求解，設 \(f_{i,j}\) 表示文本串長度為 \(i\) 的前綴後綴 \(1\) 長度為 \(j\) 的概率，\(g_{i,j}\) 表示文本串長度為 \(i\) 的前綴是目標細菌的概率。
關於 \(g_{i,j}\) 為什麼是概率而不是期望，我們發現 \(t\) 個時刻過後一共會有 \(2^t\) 個細菌，而這 \(2^t\) 個細菌互相獨立，所以我們只要先算出是目標細菌的概率，然後乘上總數就可以即可得到答案。
那麼我們考慮動態轉移方程，\(f\) 的轉移方程是非常淺顯的，設第文本串第 \(i\) 位變為 \(1\) 的概率為 \(x_i\)，則：
(1-x_i)\sum_{j=0}^{i-1}f_{i-1,j}&,\ i=0\\
x_if_{i-1,j-1} &,\ \texttt{otherwise}
\end{cases}
\]
意思非常顯然，即討論最後一個數字是不是 \(1\)，初始化 \(f_{0,0}=1\)。設 \(\mathrm{length}\) 表示給定模式串的長度，同理我們可以得到 \(g\) 的轉移：
(1-x_i)\sum_{j=0}^{i-1}g_{i-1,j}&,\ i=0\\
f_{i,j}-x_ig_{i-1,j-1} &,\ i\ge\mathrm{length}\\
x_ig_{i-1,j-1} &,\ \texttt{otherwise}
\end{cases}
\]
和 \(f\) 的轉移長得很像，一樣的部分我不多做贅述，我們發現中間有所不同，當 \(i\ge\mathrm{length}\) 時的轉移是特別的，從意思上也不難理解，即出現模式串的數量又增加了，那麼概率自然要取反，至於為什麼用是 \(f_{i,j}\) 去操作，從集合的角度，即全集減去子集得到補集，根據上面的定義，我們將 \(f_{i,j}\) 視為「長度為 \(i\) 的前綴後綴 \(1\) 長度為 \(j\) 」的全集，則 \(g_{i,j}\) 是其中一個子集，那麼轉移方程也就理所當然了。
每次的答案就是當前所有 \(g\) 的和，再乘上細胞數量，即 \(\mathrm{ans}_i=2\sum_{j=0}^ig_{i,j}\)，時間複雜度 \(\mathcal O\left(n^2\right)\)。
\(\rm subtask\ 4\)
題目給的性質 \(\mathbf B\) 反倒意義不大，這個包的重點是仍舊滿足 \(t=1\)，我們可以考慮將剛剛 \(\rm subtask\ 3\) 的單模式串問題擴展到多模式串上。
首先考慮將 \(\rm subtask\ 3\) 的情況再普遍化一點，如果這個串不只有 \(1\)，我們怎麼做，思考一番後發現我們可以使用 KMP 來解決這個問題，設 \(f_{i,j}\) 表示文本串長度為 \(i\) 的前綴長度為 \(j\) 的後綴匹配模式串長度為 \(j\) 的前綴的概率，\(g\) 定義同理，利用 KMP 的 \(\mathrm{next}\) 數組輔助轉移即可，至於上面的概率取反操作，就是當到達字元串結尾的時候要做的。
那麼用 KMP 解決單模式串問題啟示我們使用 AC 自動機解決多模式串問題，那麼剩下的就順其自然了，首先將所有串插入 AC 自動機，設 \(\mathrm{tag}_p\) 表示在節點 \(p\) 所代表的串的後綴中模板串的數量的奇偶性，然後在算 \(\mathrm{fail}\) 的同時把所有節點的 \(\mathrm{tag}\) 也一起算出來。
