题意:链接方法: FFT+Manacher解析:对于一个序列，求以任意位置(可以为间隙)为轴对称的不连续回文序列。我们不妨举一个栗子。
然后我们发现，，如果以图中的红线为对称轴的话，那么他的最长回文长度为3，也就是可非连续回文半径为3。所以大情况下这个对答案的贡献是但是其中如图所示有一些不合法的选取。也就是对于轴来说我们选取了连续，无断点的一段。我们要把这部分减掉。然而这部分恰好是以红线为轴的最长连续回文串的半径。捋一下思路。首先我们求出所有的可非连续回文半径长度，设(中间点也计算在其内)。则对答案贡献为接下里减去不合法的选取。即所有的连续回文半径长度(中间点也计算在其内)。然后考虑做法。由于n的范围是10^5所以n^2暴力找是不可取的。如果把序列中的a看做1，b看做0。则不妨举一下样例。1 0 1 1 0 1 11 0 1 1 0 1 1我们发现其实这个可非连续回文半径长度就是一个卷积的形式。两个多项式乘在一起。则前的系数恰好为以第k个位置(包括间隙，从0开始)为对称轴而对称的a的个数。这个东西显然用FFT可以在O(nlogn)内求解。但是此时我们没有算b。所以还需要将b看做1，a看做0，求一遍乘积。这样我们就完成了第一部分。而第二部分，显然Manacher裸题2333333，O(n)求即可。所以这道题就可以在O(nlogn)的复杂度下解决辣。代码:;ll;int n,m,L;char s[N];char ss[N<<1];struct complex{double r,i;complex(double x=0.0,double y=0.0){r=x,i=y;}a){return complex(r+a.r,i+a.i);}a){return complex(r-a.r,i-a.i);}a){return complex(r*a.r-i*a.i,r*a.i+i*a.r);} }a[M],b[M];int rev[M];void FFT(complex *a,int f){for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);for(int h=2;h<=n;h<<=1){complex wn(cos(2*pi*f/h),sin(2*pi*f/h));for(int i=0;i<n;i+=h){complex w(1,0);for(int j=0;j<(h>>1);j++,w=w*wn){complex t=w*a[i+j+(h>>1)];a[i+j+(h>>1)]=a[i+j]-t;a[i+j]=a[i+j]+t;}}}if(f==-1)for(int i=0;i<n;i++)a[i].r/=n;}int p[N<<1];int powtwo[N<<1];void pre(){n=strlen(s+1);ss[0]=’&’,ss[1]=’^’;for(int i=1;i<=n;i++){ss[i<<1]=s[i];ss[i<<1|1]=’^’;}n++,n<<=1;}void manacher(){int ret=0,mx=0,id=0;for(int i=1;i<n;i++){if(mx>i)p[i]=min(p[2*id-i],mx-i);else p[i]=1;while(ss[i-p[i]]==ss[i+p[i]])p[i]++;if(mx<p[i]+i)mx=p[i]+i,id=i;}}void init(){powtwo[0]=1;for(int i=1;i<=2*n;i++)powtwo[i]=(powtwo[i-1]<<1)%mod;}int ans;int f[N<<1];int main(){scanf(“%s”,s+1);n=strlen(s+1);n–;int nn=n;init();for(int i=0;i<=n;i++){a[i].r=(s[i+1]==’a’)?1:0;b[i].r=a[i].r;a[i].i=b[i].i=0;}m=2*n,L=0;for(n=1;n<=m;n<<=1)L++;for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));FFT(a,1),FFT(b,1);for(int i=0;i<=n;i++)a[i]=a[i]*b[i];FFT(a,-1);for(int i=0;i<=m;i++){int tmp=(int)(a[i].r+0.1);f[i]=f[i]+tmp;}m=2*nn,L=0;for(n=1;n<=m;n<<=1)L++;for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(int i=0;i<=nn;i++){a[i].r=(s[i+1]==’b’)?1:0;b[i].r=a[i].r;a[i].i=b[i].i=0;}FFT(a,1),FFT(b,1);for(int i=0;i<=n;i++)a[i]=a[i]*b[i];FFT(a,-1);for(int i=0;i<=m;i++){int tmp=(int)(a[i].r+0.1);f[i]=f[i]+tmp;}for(int i=0;i<=m;i++){int tmp=(f[i]+1)/2;if(tmp>=0)ans=(((ans+powtwo[tmp])%mod-1)%mod+mod)%mod;}pre();manacher();for(int i=0;i<=n;i++)ans=((ans-p[i]/2)%mod+mod)%mod;printf(“%d\n”,ans);}
找一个让心里安静和干净的地方，
