题意：
给出一个长度为偶数的字符串S，要求把S分成k部分，其中k为任意偶数，设为a[1..k]，且满足对于任意的i，有a[i]=a[k-i+1]。问划分的方案数。
n<=1000000
题解：
反正我是不会做 （我是转载的yyb博客，巨佬写的超级超级）
基本就是照着laofulaofu的打了一遍（laofu太强啦）这题分成了两个步骤
如果直接分kk段我们是没法直接判断的假设两段si,sk−i+1因为si=sk−i+1=x1x2.....xj 假设si的开始位置为p假设原串S的长度为nsi=S[p]S[p+1]....S[p+j−1]sk−i+1=S[n−j−p+1]S[n−j−p+2]...对应相等的关系是S[p]=S[n−p−j+1]如果p=1考虑一下特殊情况那么就是S[1]=S[n−j]那么，如果我们有一个串S′S′=S[1]S[n]S[2]S[n−2].....那么，对应到上面的相等关系里面，就是S′[1..j]是一个回文串其他的每一组对应关系也是如此所以题目转换成了：告诉你了S′回答把S′分为若干个长度为偶数的回文串的方案数（如果没有搞清楚可以手玩一下）这个就是一个裸的dp了设f[i]f[i]表示S′[1..i]S′[1..i]划分为若干长度为偶数的回文串的方案数得到转移方程：
f[i]=∑jf[j−1]
其中，S′[j,i]S′[j,i]是回文串那么，每一个jj对应的位置相当于是S′[1..i]S′[1..i]的回文后缀构建出回文树之后沿着last跳fail就可以得到所有的j的位置
这样子的复杂度是O(回文串数量)的，显然会超时，考虑如何优化。 有一个小结论就是一个回文串S的一个后缀T是回文串当且仅当T是S的border。 有一个性质就是一个串的所有border可以划分成O(log)段等差数列。
维护pre[p]表示节点p下一个等差数列的末项。 d[p]表示公差
1 #include2 #include