【题意】给定只含'a'和'b'字符串S，求不全连续的回文子序列数。n<=10^5。
【算法】FFT+回文串
【题解】不全连续的回文子序列数=回文子序列总数-回文子串数。
回文子串数可以用回文串算法（Manacher，PAM，二分+hash）轻松计算。
设f[i]表示以i为对称中心的对称字符对数，那么 i 对答案的贡献是$2^{f[i]}-1$，同时容易列出f[i]的计算公式：
$$f[i]=sum_{j=0}^{i}[S_j=S_{2i-j}]$$
令a=0，b=1，那么有：
$$f[i]=sum_{j=0}^{i}S_j*S_{2i-j}$$
这是一个卷积的形式，将上届扩展到2*i就可以计算了，同理计算a=1,b=0。
同理计算以i和i+1中间为对称中心的答案。
也可以用manacher那种方式处理字符串。