「Wdsr-3」蓬莱药局 题解

· · 题解

更好的阅读体验

你谷 link

综合性比较强的 AC 自动机题目，我们可以对这道题逐步分解求解。

\rm subtask\ 1

没有变换，问题转化成多模式串单文本串，求文本串的每个前缀的模式串出现次数，AC 自动机模板题，也可以用后缀数据结构解决，这里不多做解释，可以出门左转你谷模板区自行学习（AC 自动机模板都不会就来刷字符串黑题？），时间复杂度就是 AC 自动机模板的时间复杂度 \mathcal O\left(n+k\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，则：

f_{i,j}=\begin{cases} (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 的转移：

g_{i,j}=\begin{cases} (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} 也一起算出来，运用 tag 来支持我们的 dp，转移方程由于 AC 自动机认子不认父的结构，写成枚举起点转移别人的方式会更加简单，直接根据 AC 自动机的 trie 图转移就好了，等所有都转移好了再将满足 \mathrm{tag}_p=1 的 p 对应的 g 全部取反，实现难度不大，时间复杂度 \mathcal O\left(nk\sum|g_i|\right)。

\rm subtask\ 5,6

到这里就是正解了，我们发现我们现在唯一的障碍就是 t>1，但是我们在前面讲 \rm subtask\ 3 的时候讲到我们分裂得到的每个细胞是互相独立的，那么 t 影响的实际上就是数列中每个数变成别的数的概率，我们只要知道 t 个时刻后每个数变成另一个数的概率直接套用 \rm subtask\ 4 的做法就好了，我们发现可以对给定的 P 矩阵做矩阵快速幂，P 矩阵的 t 次方即我们所求，这样就做完了，时间复杂度 \mathcal O\left(k^3\log t+nk\sum|g_i|\right)。

具体代码实现方面，整份代码本来是数据点分治，\rm subtask\ 1 部分 n 与 \sum|g_i| 较大，直接用后面的做法会 TLE，要特殊处理，而后面 \rm subtask\ 3 的 k 较大，在矩阵快速幂过程中 k^3 与单位矩阵相乘一次会直接 TLE，但是这些都可以解决，我们一定要建出 AC 自动机，且与后面的 AC 自动机一致，所以 \rm subtask\ 1 可以在建出 AC 自动机后几行解决，\rm subtask\ 3 实际我们在转移过程中有用的可以压缩成 1/2，将所有不是 1 的转移压缩到 2 上，矩阵压缩成 k\times 2 的，虽然不能矩阵幂，但是矩阵乘一次是可以接受的，就可以减少很大一部分特判，剩下的部分直接和正解部分合并就好了，代码并不麻烦。

c++ 代码