FFT好题~

我们观察一波性质 首先 回文的子序列一定是 j+k=i 其中j和k分别是两个下标 然后i是固定的

这玩意看起来是不是就很像卷积= =+

我们要求的是f[i]就是固定值是i的时候两侧的相同字符对数

然后呢 我们分别把a和b做一遍

a就是把一个位置上是a的赋成1然后FFT自乘 b同理

a，b对应系数相加就得到了f[i]

求答案就是枚举所有i求2^f[i]-1

但是题目还要求不能连续 所以 我们跑一遍manacher去掉就好啦

然后我写了一个神奇小错误

我最开始枚举i是从1开始枚举的导致我所有答案都小1QAQ

然后立flag +1过了emm

后来我发现 我的i特么怎么是从1开始的！！！改过来以后就不用加1了QAQ

原因其实就是 f[0]肯定是等于1的[0的字符=0的字符]那么 2^1-1=1 是个定值。。。

所以就很资磁。

附代码。

#include
    
     #include
     
      #include
      
       #include
       
        #define inf 20021225#define ll long long#define mdn 1000000007#define db double#define mxn 410000using namespace std;const db PI=acos(-1.0);int ksm(int bs,int mi){	int ans=1;	while(mi)	{		if(mi&1)	ans=(ll)ans*bs%mdn;		bs=(ll)bs*bs%mdn; mi>>=1;	}	return ans;}int rev[mxn],inv;int init(int n){	int lim=1,l=0;	while(lim
        
         >1]>>1)|((i&1)<<(l-1));	inv=ksm(lim,mdn-2);	return lim;}struct complex{	db x,y;	complex(){}	complex(db _x,db _y){x=_x;y=_y;}}sa[mxn],sb[mxn];complex operator+(complex a,complex b){return complex(a.x+b.x,a.y+b.y);}complex operator-(complex a,complex b){return complex(a.x-b.x,a.y-b.y);}complex operator*(complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y);}void fft(complex *a,int n,int f){	for(int i=0;i
         
          i) swap(a[rev[i]],a[i]); for(int k=2;k<=n;k<<=1) { int mid=k>>1; complex Wn = complex(cos(PI/mid),f*sin(PI/mid)); for(int i=0;i
          
           =0&&ch[i+f[i]]==ch[i-f[i]]) f[i]++; if(i+f[i]>mr) mr=i+f[i],md=i; ans=(ans-(f[i]>>1)+mdn)%mdn; }}void work(){ //printf("%lf\n",PI); for(int i=0;i
           
            >1)-1,ans=(ans+tmp)%mdn; } manacher(); printf("%d\n",ans);}int main(){ scanf("%s",a); n=strlen(a); work(); return 0;}