题意

给你一个长为\(n\)的字符串\(S\)，现在你要把他划分成\(k\)段，记为\(p_1p_2…p_k\)，其中对于任意\(1<=i<=k\)，满足\(p_i=p_k−i−1\)，且\(k\)为偶数。问划分方案数。
n<=1e6

做法

将\(S=s_1s_2s_3...s_{n-2}s_{n-1}s_n\)，转化成\(S'=s_1s_ns_2s_{n-1}s_3s_{n-2}...\)，这样问题就变成了划分偶回文串
利用PAM可以做到\(O(n^2)\)

PAM中的节点的等差数列个数是\(O(logn)\)的
然后每个节点维护其到上面一段等差数列

考虑\(i\)，当前有最大的几个回文后缀\(s_{i-a,i},s_{i-b,i},s_{i-c,i}(a-b=b-c=d)\)，也就是\(f_{i-a-1},f_{i-b-1},f_{i-c-1}\)会产生贡献
手玩一下能发现\(f_{i-a-1},f_{i-b-1}\)会对\(f_{i-d}\)产生贡献，也就是之前已经被维护过了，就只用格外把\(f_{i-c-1}\)维护进来即可
那么\(s_{i-a,i-d}\)

题外话

还菜啊...远古题都做不动...