Palindrome Partition(回文划分计数)

发布时间 2023-12-03 11:04:55作者: kyEEcccccc

首先把原串交错重构,使得转化为偶回文串划分计数,不讲(虽然很难想到)。下面先考虑回文划分计数。容易得到一个 DP:\(f_i\) 表示长度为 \(i\) 的前缀划分方案数,则枚举所有 \(i\) 结尾的回文子串即可进行转移。我们可以求出以 \(i\) 结尾的最长回文后缀,通过不断跳它在回文树上的 fail 得到所有回文后缀。时间复杂度 \(\Theta(n^2)\)

下面考虑优化这一过程。一个结论是回文串的回文后缀和它的 border 是同一个东西。而我们有任何一个字符串的 border 可以划分成不超过 \(\log n\) 段等差数列的结论。所以在回文自动机上,设 \(dif_u\) 表示 \(len_u - len_{fail_u}\),又有 \(slink_u\)\(u\) 最近的祖先,使得 \(dif_{slink_u} \neq dif_u\)。这样,从任何一个节点跳 \(slink\) 链一直到奇根,只需要 \(\log n\) 次。注意到这实际上是一种树链剖分,我们自然考虑在链上记录前缀信息来优化转移,具体地设 \(g_u\) 表示回文树上节点 \(u\) 对应的回文串最后一次出现时,它前面一个位置的 \(f\) 值,维护 \(G_u\) 表示 \(u\)(含)一直到 \(slink_u\)(不含)这条链上所有节点的 \(g\) 值之和。当然,我们事实上并不保证在任何时刻每个节点的 \(G\) 值都是正确的,但是可以保证一个节点 \(u\) 被用到时将它的 \(G\) 值更新正确。

考虑一段等差数列的起点,节点 \(u\) 对应的串,假设它是 \(S\)\(dif_u\) 实际上就是 \(S\) 的一个周期。这也告诉我们,等差数列上除了 \(S\) 本身以外的每个串都可以向前平移 \(dif_u\),同时分析可得,这正是它上一次出现的位置。考虑 \(G_u\) 的数值和 \(G_{fail_u}\) 的差,由于上面的平移结论,容易发现只相差了 \(f[i - len[slink_u] + dif_u]\) 这个位置。而 \(G_u\) 的数值在 \(i - dif_u\) 处被用到,一定被更新正确,所以这里只要直接加一下即可。时间复杂度 \(\Theta(n\log n)\) 可以通过。

在这道题中我们只允许偶回文串。考虑 \(G_{0/1}\) 记录来自偶数下标和奇数下标的 \(f\) 值即可。