【bzoj3160】万径人踪灭
题意
给定一个由'a'和'b'构成的字符串，求不连续回文子序列的个数。
\(n\leq 100000\)
分析
还是蛮不错的。
这道题基本上是自己想到的。
除了没有利用到'a'和'b'只有两个不同字符的特性。
求不连续回文子序列的个数。
首先问题可以进行转化：
根据容斥原理，用任意回文子序列的个数（1）-连续回文子序列（2）的个数。
问题（2），即连续回文子序列的个数，用Manacher很容易求出来。
所以现在考虑解决问题（1）：任意回文子序列的个数。
我们的想法是枚举每条对称轴\(i\)，然后考虑对称轴的左右：若该点距离对称轴的距离为\(a\)，则\(a\)可以选，当且仅当\(s[i-a]=s[i+a]\)。而两个距离不同的点对的选择互不影响。
所以我们设\(f[i]\)表示以\(i\)为对称轴的可选点对的个数，即\(f[i]=\sum_a [s[i-a]=s[i+a]]\)，其中\([a]\)的定义是：若布尔值\(a=true\)，则\([a]=1\)，否则\([a]=0\)。
由于每个可以选，可以不选，且互不影响，所以答案即是\(\sum_{i为对称轴} 2^{f[i]}\)
关键怎么快速的求\(f[i]\)。
暴力的求法肯定不行，时间复杂度为\(O(n^2)\)。
考虑如何优化求\(f[1],f[2],...,f[n]\)。
还有一个特性没有使用到：就是字符串中的每一个字符只有两种情况：'a'，'b'。
不妨再分类来想：我们先求出\(s[i-a]=s[i+a]='a'\)的个数，再求出\(s[i-a]=s[i+a]='b'\)的个数，然后相加。
二者问题的形式相同，所以只要能解决\(s[i-a]=s[i+a]='a'\)的个数，另一个问题亦能解决。
注意到，对于一个位置\(i\)，对于一个确定的距离\(a\)，点对的和为\((i-a)+(i+a)=2i\)，即点对的和一定。
所以我们设\(w[i]=[s[i]=='a']\)。
这样，对于一个位置\(i\)，若\(i-a\)和\(i+a\)对它有贡献，当且仅当\(w[i-a]*w[i+a]==1\)，否则一定没有贡献。
所以我们只需要求第\(2i\)个位置上的值即可。
用FFT即可解决。
上面忽略了一个细节，也是为了行文的流畅性。
就是对称轴可能不在一个字符串上，而可以在两个字符串中间。
如何解决？
只需要把两个字符串中间添加一个虚拟点即可。
小结
（1）计数问题
- 容斥原理（转化手段）
- 枚举（转化手段）
- 排列组合（快速求法）
- 动态规划（分阶段）