CF932G 题解

zhylj · 2021-02-23 21:51:46 · 题解

题目描述

把字符串 s 划分成若干个字符串 t_1t_2\cdots t_k，使得 t_i=t_{k-i+1}，求方案数，对 998244353 取模。

故 \operatorname{pre}(u,|u|-d) 为 u 的一个 border，即 d 为 u 的一个周期，同理 q 为 u 的一个周期。

而显然第一次匹配和第 x 次匹配的位置集合 u_1,u_x 同样存在重叠部分，故 d+q\le |u|，故 \gcd(d,q) 为 u 的周期。

若 d< \gcd(d,q)，则我们可以将 u_2 向前移动构造在第一次第二次之间的匹配，矛盾。

故 d = \gcd(d,q)，即 d\mid q。

由 u_i = u_{i+d}，我们可以得到从第二次匹配开始到第 x 次匹配，每隔 d 个字符均会存在一个匹配，故命题得证。

由此证明我们可以得到一个推论：

推论：若字符串 u,v 满足 |u|\le |v|\le 2|u|，u 在 v 中的所有匹配位置构成了一个公差为 d，超过三项的等差数列，则 \operatorname{per}(u) = d.

接下来我们讨论 Border 的结构。

引理：字符串 s 的所有不小于 |s|/2 的 border 组成一个等差数列。

证明：对于最大的 border 和任意一个 border，设其长度分别为 n-p,n-q，可得 p,q 为 s 的周期，\gcd(p,q) 为 s 的周期，类似之前的方法可得 p\mid q。

（border 本质上就是在和自己匹配）

引理：若 |u|=|v|，记 \operatorname{LargePS}(u,v)=\{k\mid k\ge |u|/2,\operatorname{pre}(u,k)=\operatorname{suf}(v,k)\}，则 \operatorname{LargePS}(u,v) 构成一个等差数列。

证明：设其中最大的元素为 x，则 x/2\le |u|/2，且其他元素均为 \operatorname{pre}(u,x) 的 border 的长度。接下来由前一个引理可证。

我们可以把一个字符串的所有 border 按照长度属于 [1,2),[2,4),\cdots,[2^k,n) 分类，第 i 类的元素为 \operatorname{LargePS}(\operatorname{pre}(s,2^i),\operatorname{suf}(s,2^i)).

于是我们得到了一个推论：

推论：字符串 s 的 border 可以被划分为 \mathcal O(\log n) 个等差数列。

回文后缀与 border

引理：s 是回文串，则 s 的后缀 t 是回文串当且仅当 t 是 s 的 border.

证明

两个条件均等价于 s_i = s_{|s|-i+1} = s_{|s|-(|t|-i + 1)+1} = s_{|s|-|t|+i}.

据此，易得：

推论：s 是回文串，则 s 的回文后缀可以被划分为 \mathcal O(\log n) 个等差数列。

slink 链与最小回文划分

slink 指针

记 \operatorname{diff}(x) = \operatorname{len}(x) - \operatorname{len}(\operatorname{fail}(x))，而 \operatorname{slink}(x) 表示回文树中 \operatorname{fail} 树上离 x 最近的满足 \operatorname{diff}(y)\neq \operatorname{diff}(x) 的 y。

显然这可以很容易在建回文树的时候维护出来。

容易发现，这意味着从 x 开始跳 \operatorname{fail} 指针，一直到跳到 y 之前，都是在一个等差数列上跳的。

也就是说，根据我们之前的推论，从某个点开始跳 slink 指针直到根节点，至多跳 \mathcal O(\log n) 步。

回文划分计数

例：给定一个字符串 s，求有多少划分 t_1t_2\cdots t_n = s，使得 t_1,t_2,\cdots,t_n 均为回文串。对 998244353 取模。