总结

啊哈，今天腊月初一。继续昨天的专题。字符串，很有趣啊。

[CTSC2006] 歌唱王国

要用到 PGF。概率生成函数。这类题，大概就是设置两个看起来相反的函数。比如这道题就设置一个表示在位刚好结束，表示在位还没有结束，容易发现生成函数，然后在每个 G 串后加一串原串，会发现这些字符串和 F 中字符串后加一些周期是相等的。式子就出来了。

E. 二指禅

和 2023-12-16 nfls 模拟 的 C 一样。当时数据范围是 200000，这道题是 300000，是 ROI 的原题。简单回顾了一下思路然后思考了一下实现过程，由于代码量太大不想写了……然后就贺了之前的代码该了一下数据范围，然后 LOJ 上面 A 了，nflsoj 上 TLE 了。尝试卡常。把块长改成 1000 就能过了。

Tokitsukaze, CSL and Palindrome Game

容易发现就是上一道题的拓展版本。由于回文串可以很方便地通过 PAM 来维护和查找，所以建立 PAM 后在 fail 树上用个 hash 然后倍增跳就行。HDU 上面要卡一下常数，写个快读就可以了。这个 hash 乱搞都能过。

CF1483F Exam

AC 自动机。容易找到所有前缀最大后缀的字符串。然后从后往前，如果没有被包含就加入统计。然后再开一个 BIT，用来计算当前字符串中某个字符串一共出现了多少次，两个要相等才有贡献。

后记

还是颇有收获的。感觉真奇妙。