【题意】给定只含'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那种方式处理字符串。

优质内容筛选与推荐>>
1、ETL工具-Kattle：查询 HTTP/WebService
2、安装informatica8.6.1遇到的问题
3、BZOJ1172 : [Balkan2007]Dream
4、第3章 （五）目录树结构、挂载
5、CSS选择器

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

阅读

已发送

发送中