题解：qoj#8306 Boring Problem
complexor
·
·
个人记录
有趣的题目。
题意简述
给出 n 个长度为 m 的字符串 t_1,t_2,\dots,t_n，都由前 c 个小写字母组成。
定义 E(S) 为当前有字符串 S，每过 1 秒，会在 S 后面随机接一个字母，其为第 i(1\leq i\leq c) 个小写字母的概率是 p_i，期望多少秒后 t_1,t_2\dots,t_n 中的至少一个会作为子串出现。
现在给定字符串 T，求出对于 T 的每个前缀 T[1:i]，求出 E(T[1:i])。
## 解法
$n=1$ 时是 [P4548 [CTSC2006] 歌唱王国](https://www.luogu.com.cn/problem/P4548)。不过这个题数据范围较小，不太可能是简单结论。
对于 $n>1$ 的情况，不妨设 $t_i$ 互不相同。
多串匹配，考虑建出 AC 自动机。设若当前在 $x$，加上字符 $i$ 转移到结点 $tran(x,i)$，期望需要 $E(x)$ 秒匹配上，那么有：
$$
\begin{aligned}
E(x)=\begin{cases}
0&,x为终止结点\\
\displaystyle\sum_{i=1}^cp_iE(tran(x,i))+1&,O.W.
\end{cases}
\end{aligned}
$$
AC 自动机总结点数是 $O(nm)$ 的，直接高斯消元求出所有 $E$ 是 $O(n^3m^3)$ 的。
上面的方程有 $O(nm)$ 个变量，考虑利用这些约束的特殊性进行手动消元/代换，以减小变量数量再高斯消元。
AC 自动机是基于 trie 树的，记结点 $x$ 在树上的深度为 $dep(x)$，我们现在按深度一层一层地处理 $E(x)$。先将根结点设为变量。假设当前我们已经处理完所有 $dep(x)\leq D$ 的 $x$，那么考察每个 $dep(x)=D$ 的 $x$，对于每个 $i=1,2,\dots,c$：
- 若 $dep(tran(x,i))\leq D$，那么 $E(tran(x,i))$ 已经处理过了。
- 若 $dep(tran(x,i))> D$，那么根据 AC 自动机的性质可以发现，$tran(x,i)$ 一定是 $x$ 在 trie 树上的子结点。设这样的点有 $ch_x$ 个，那么由 $E(x)=\sum_{i=1}^cp_iE(tran(x,i))+1$，可以将其中的 $ch_x-1$ 个子结点的 $E$ 设为变量，就可以算出剩下的那个子结点的 $E$。
在上面的过程中，总变量数量为 $1+\sum_x\max\{0,ch_x-1\}=\sum_x[ch_x=0]$， 也就是叶子数量 $n$。而对于每个叶子 $x$，$E(x)=0$ 的约束在上面也没有用到。所以我们得到了 $n$ 个变量和 $n$ 个约束，可以证明足以求解出所有变量，进而求出所有 $E$。
最后只需要拿 $T$ 在 AC 自动机上跑一遍，注意处理 $T[1:i]$ 中已经出现一个 $t$ 的情况。
将每个 $E$ 表示为 $n$ 个变量的线性组合复杂度为 $O(n^2mc)$，高斯消元复杂度为 $O(n^3)$，总复杂度为 $O(n^2mc+n^3+|T|)$。