自动搬运

查看原文

来自洛谷，原作者为

	happybob **

搬运于2025-08-24 23:12:29，当前版本为作者最后更新于2025-04-11 22:40:37，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑给定 $s_1,s_2,s_3$，如何计算 $f(s_1,s_2,s_3)$。

从前往后考虑每个 $t_i$ 是多少，发现若 $t_i$ 为 $s_{1/2/3,i}$ 中出现次数最大的那个，则相当于对后面的字符有一些限制，这些限制只和这次出现次数较大的那些串是什么而与其他无关，若 $t_i$ 为出现次数少的那个，则 $t$ 之后的值必然是对应的 $s$ 后面的值。

于是可以从前往后进行 DP，记 $f_{i,S}$ 表示已经填了 $[1,i]$，之前每次取的都是出现次数较大的字符，$(1,2),(1,3),(2,3)$是否作为过出现次数最大的两个时的概率，转移 $2^3$ 枚举所有可能情况即可。