“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}\) 也一起算出来。
