今天被课表上写着dp，pdf标题是图论的线性代数薄纱了。
下午抽时间看了看明天的课件，发现了喜报：明天没有紫题?！于是晚上就把课件里面第一道题给赫题解赫过去了?
看了看初三他们集训的课件捏，发现 PAM 突然不会了?，赶忙恶补了下 PAM，为此还发了两个帖子，没人回。
PAM 中的回文子串划分，指的是把一个字符串 \(\text{A}\) 划分为一堆段，满足这些段都为回文串，求方案数/最小回文划分。
数据范围 \(|A|\le 10^5\)。
这里只说求方案数。考虑 dp，设 \(f_i\) 为前 \(i\) 个字符回文划分的方案数，则有下面的转移方程：
考虑用 PAM 优化这个转移方程。首先有一个引理，即一个回文串的回文后缀按长度排序会形成 \(O(\log n)\) 个等差数列。具体证明可以翻 OIWIKI。有了这个定理后我们维护两个数组：\(diff[i]\) 表示 \(i\) 与 \(fail[i]\) 的长度差，\(slink[i]\) 表示一直跳 \(fail\)，直到第一个跳到 \(diff[i]\) 不相等的位置，也就是一段等差数列之后的下一个位置。根据引理，暴力跳 \(slink\) 的复杂度为 \(O(\log n)\)。因此我们考虑把一段等差数列的 \(f\) 值记在最长的那一段上，记作 \(g\)。
有了这个 \(g\) 之后我们只需要每次暴跳 \(slink\) 统计答案就好。而对于新加进来的字符，我们考虑会对之前的等差数列有什么贡献，下面放出洛谷题解区的几张图：
第一张图中的绿线代表的是在 \(i\) 位置需要计算 \(g\)，第二张图的绿线表示的是在 \(i-diff[p]\)，也就是 \(fail[p]\) 这个位置代表的 \(g\)，可以看到，它们相差了 \(f[i-diff[p]-len[slink[p]]]\)。这样就可以递推出来了。
时间复杂度 \(O(n\log n)\)。
恋恋可爱捏?