Description

Input

Output

Sample Input

Sample Output

HINT

Source

2013湖北互测week1

首先将字符串中间插入”#” 把他们分隔开

题目要求求不连续的回文串的个数 那么就用总数减去连续的即可 考虑连续的部分 直接用manacher求即可 算出长度 然后再/2就是答案

不连续的怎么办 考虑现在用#将他们隔开 然后假如只考虑字符是a的贡献

那么 显然字符a都会出现在偶数位置上  那么想办法知道一个位置左右对称的符合要求的字符即可得到答案 比如#a#b#a这样关于b左右对称的就是2 然后答案就是2^2-1

那么想办法计算出左右对称位置符合要求的这个t即可

设当前在第k位

$f[k]=\sum\limits_{i}^{不越界}[k-i\mod 2=0][s_{k-i}=’a’][s_{k+i}=’a’]$ $\sum\limits_{t}\sum\limits_{i}^{不越界}[k-i=2\times t][s_{\frac{k-i}{2}}=’a’][s_{\frac{k+i}{2}}=’a’]$ $\sum\limits_{t}\sum\limits_{i}^{不越界}[k-i=2\times t]s_{t}*s_{k-t}$ $\sum\limits_{t}[k-2*t>=0]s_{t}*s_{k-t}$ $\sum\limits_{t=0}^{\lfloor\frac{k}{2}\rfloor}s_{t}*s_{k-t}$ s即表示该串这个位置是否为a|b为的话就是1

然后两次dft一次idft即可

 

分类: fft

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论

电子邮件地址不会被公开。 必填项已用*标注