自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:33:14，当前版本为作者最后更新于2021-08-23 22:49:18，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

有删减，原文见我的博客。

很有意思的一道题。

不难发觉得关键还是在变化上。

我们用 $1,2,3$ 表示分别表示三个字母，那么如果 $c_1\neq c_2$，则 $c_3 = c_1 \oplus c_2$，直接异或就行。

但是如果 $c_1=c_2$ 根本表示不了，后面也没法做（罚坐了半个小时

考虑用 $0,1,2$ 分别表示三个字母，那么我们可以发现 $c_3\equiv-c_1-c_2\pmod{3}$。

所以杂交后得到的串 $S$ 一定可以表示为 $aS_A+bS_B+cS_C$，由于每一位都是模 $3$ 意义下的，所以杂交所得的串不会超过 $27$ 个。

我们直接写个程序爆算所有可能的 $(a,b,c)$，发现只有 $9$ 种可能。

那么我们只用预处理这 $9$ 个串的哈希值，然后用线段树维护 $T$ 的哈希值，这道题就做完了。