【Codeforces932G】Palindrome Partition


题意

询问能将给定的字符串分割成多少合法的形式。一个分割形式是合法的,是指,讲一个字符串分割成 \(k\) 个子串,其中 \(k\) 是偶数,而且对于分割出来的子串 \(a_1,a_2,\cdots ,a_k\) ,需要满足 \(a_1=a_k,a_2=a_{k-1},\cdots \) 。

分析

字符串变幻

直接处理没有什么直接的思路。首先考虑将字符串变形。

将字符串变为 \(s_1s_ns_2s_{n-1}s_3s_{n-2}\cdots s_{\frac{n}{2}}s_{\frac{n}{2}+1}\) 。

这样变形以后,对于上述分割出来的任意子串 \(a_i=a_{k-i+1}\) ,可以观察到:

假设 \(a_i=s_{l}s_{l+1}\cdots s_r\) ,则 \(a_{k-i+1}=s_{n-r+1}s_{n-r}\cdots s_{n-l+1}\) ,其中需要满足的是 \(s_l=s_{n-r+1},s_{l+1}=s_{n-r},\cdots ,s_{r}=s_{n-l+1}\) 。

在变换后的字符串中 \(s_{l},s_{n-l+1},s_{l+1},s_{n-l},\cdots s_r,s_{n-r+1}\) 是一个连续的子串,而需要满足的要求,无非是规定了这个子串是一个长度为偶数的回文串。

这样一来就变成了求有多少方案将字符串分割成若干个长度为偶数的回文串。

考虑 dp

这样的 dp 想法就比较直接了。

用 \(f[i]\) 表示考虑了前 \(i\) 位分割以后的方案数,那么显然,转移方程就是

\(f[i]=\sum f[j] (j < i)\) 其中 \(s_{j+1}\cdots s_i]\) 构成长度为偶数的回文串。

对于当前的 \(i\) ,可以用 PAM 辅助转移,时间复杂度 \(O(n^2)\) ,无法通过此题。

考虑优化

我们利用 Palindrome Series 的性质,进行优化。

用一个新的状态 \(g[i]\) 记录从当前状态到包含当前状态的 border 的长度构成的等差数列首状态的信息。

利用 Palindrome Series 的性质,对于当前所在类,假设当前状态 \(x\) 所在的等差数列 border 的长度包含了 \(a,b,c\) 且 \(a>b>c,d=a-b=b-c\) ,那么现在 \(g[x]\) 应该包含的信息有 \(f[a],f[b],f[c]\)。

那么显然有 \(s[i-b,i]=s[i-a,i-d],s[i-c,i]=s[i-b,i-d]\) ,而显然 \(fail[x]\) 的位置指向长度为 \len[x]-c\) ,也就是说 \(g[fail[x]]\) 已经包含了 \(f[a],f[b]\) ,也就是只需要在加上 \(f[c]\) 的信息,而 \(c\) 显然就是当前状态所表示的最小 border 长度。

由等差数列的维护可以得到,当前状态最小的 border 长度为 \(len[anc[x]]+diff[x]\) ,于是,应该是状态 \(f[i-len[anc[x]]+diff[x]]\) 。

而对于偶数长度的处理,我们只需要保证只有所有的偶数 \(i\) 的 \(f[i]\) 是包含有效信息的即可。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 75,676

Categories

Archive

Comments