专栏文章

题解：qoj#8306 Boring Problem

ccomplexor管理员
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8giwn
此快照首次捕获于
2025/12/03 07:52
3 个月前
此快照最后确认于
2025/12/03 07:52
3 个月前
查看原文
有趣的题目。

题意简述

给出 nn 个长度为 mm 的字符串 t1,t2,…,tnt_1,t_2,\dots,t_n，都由前 cc 个小写字母组成。
定义 E(S)E(S) 为当前有字符串 SS，每过 11 秒，会在 SS 后面随机接一个字母，其为第 i(1≤i≤c)i(1\leq i\leq c) 个小写字母的概率是 pip_i，期望多少秒后 t1,t2…,tnt_1,t_2\dots,t_n 中的至少一个会作为子串出现。
现在给定字符串 TT，求出对于 TT 的每个前缀 T[1:i]T[1:i]，求出 E(T[1:i])E(T[1:i])。
n≤100,nm≤104,c≤26,∣T∣≤104n\leq 100,nm\leq10^4,c\leq 26,|T|\leq 10^4。

解法

n=1n=1 时是 P4548 [CTSC2006] 歌唱王国。不过这个题数据范围较小，不太可能是简单结论。
对于 n>1n>1 的情况，不妨设 tit_i 互不相同。
多串匹配，考虑建出 AC 自动机。设若当前在 xx，加上字符 ii 转移到结点 tran(x,i)tran(x,i)，期望需要 E(x)E(x) 秒匹配上，那么有：
E(x)={0,x为终止结点∑i=1cpiE(tran(x,i))+1,O.W.\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)O(nm) 的，直接高斯消元求出所有 EE 是 O(n3m3)O(n^3m^3) 的。
上面的方程有 O(nm)O(nm) 个变量，考虑利用这些约束的特殊性进行手动消元/代换，以减小变量数量再高斯消元。
AC 自动机是基于 trie 树的，记结点 xx 在树上的深度为 dep(x)dep(x)，我们现在按深度一层一层地处理 E(x)E(x)。先将根结点设为变量。假设当前我们已经处理完所有 dep(x)≤Ddep(x)\leq D 的 xx，那么考察每个 dep(x)=Ddep(x)=D 的 xx，对于每个 i=1,2,…,ci=1,2,\dots,c：
  • 若 dep(tran(x,i))≤Ddep(tran(x,i))\leq D，那么 E(tran(x,i))E(tran(x,i)) 已经处理过了。
  • 若 dep(tran(x,i))>Ddep(tran(x,i))> D，那么根据 AC 自动机的性质可以发现，tran(x,i)tran(x,i) 一定是 xx 在 trie 树上的子结点。设这样的点有 chxch_x 个，那么由 E(x)=∑i=1cpiE(tran(x,i))+1E(x)=\sum_{i=1}^cp_iE(tran(x,i))+1，可以将其中的 chx−1ch_x-1 个子结点的 EE 设为变量，就可以算出剩下的那个子结点的 EE。
在上面的过程中，总变量数量为 1+∑xmax⁡{0,chx−1}=∑x[chx=0]1+\sum_x\max\{0,ch_x-1\}=\sum_x[ch_x=0]， 也就是叶子数量 nn。而对于每个叶子 xx，E(x)=0E(x)=0 的约束在上面也没有用到。所以我们得到了 nn 个变量和 nn 个约束，可以证明足以求解出所有变量，进而求出所有 EE。
最后只需要拿 TT 在 AC 自动机上跑一遍，注意处理 T[1:i]T[1:i] 中已经出现一个 tt 的情况。
将每个 EE 表示为 nn 个变量的线性组合复杂度为 O(n2mc)O(n^2mc)，高斯消元复杂度为 O(n3)O(n^3)，总复杂度为 O(n2mc+n3+∣T∣)O(n^2mc+n^3+|T|)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...