Descriptions:


题解:


多好的题啊~
题目大意:求给定只包含'a','b'的字符串的不连续回文子序列个数.
我们可以把所有的回文子序列的数目减去连续的回文子序列个数,后者可以用Manacher解决.
\(f[i]\) 表示以 \(i\) 为回文中心的回文子序列长度,可以发现回文子序列的数目就是 \(\sum_{i=0}^{n} 2^{\frac{f[i]+1}{2}}-1\)
然后可以发如果两个字符相等会给它们的中心的f值贡献1.
这个满足卷积的性质,接下来就可以把'a'当做1卷积一次,然后把'b'当做1卷积一次.

用Manacher扩大一倍后的字符串去卷积TLE了一发QAQ