题解：P12057 [THUPC 2025 决赛] 好串

· · 题解

考虑给定 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 枚举所有可能情况即可。