自动搬运

查看原文

来自洛谷，原作者为

	老莽莽穿一切 车万厨 Jo厨 锦依卫 舟游人 都是我

搬运于2025-08-24 22:35:09，当前版本为作者最后更新于2022-07-25 18:40:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

更好的阅读体验

---

你谷 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++ 代码