【bzoj3160】万径人踪灭

题意:给一个只含a、b的字符串,求所有的回文不连续子序列。

manacher+FFT。

先求出所有回文序列,再减去连续子序列(即回文串)。

将a、b分开考虑,对于一个对称轴,以其为回文中心的回文序列的个数为 2^对称a、b个数-1。对称统计显然可以通过FFT求,然后再用manacher求回文串1即可。

调的好恶心啊!

上一篇:Lintcode: Product of Array Exclude Itself


下一篇:ThreadLocal详解(实现多线程同步访问变量)