3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB

Description

Source

不难发现，ans=总方案 – 连续子串

考虑总方案，枚举对称轴，方案数就是2^f(i) -1，f(i) 表示有多少对关于对称轴对称

那么如何求f(i)，

很容易发现式子就是FFT卷积，那就把a,b拆开分别求一遍FFT就好了

连续的就直接manacher咯

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 200010
#define PI 3.141592653589793
struct cp{
	double r,i;
	cp(double _r=0,double _i=0):r(_r),i(_i){}
	cp operator + (cp x){return cp(r+x.r,i+x.i);}
	cp operator - (cp x){return cp(r-x.r,i-x.i);}
	cp operator * (cp x){return cp(r*x.r-i*x.i,r*x.i+i*x.r);}
	void clr(){r=i=0.0;}
};
cp A[N],B[N];
int r[N],L=-1;
void FFT(cp *x,int n,int f)
{
	register int i,j,k;
	for(i=0;i<n;i++) if(i<r[i]) swap(x[i],x[r[i]]);
	for(i=1;i<n;i<<=1)
	{
		cp wn(cos(PI/i),f*sin(PI/i));
		for(j=0;j<n;j+=i<<1)
		{
			cp w(1,0),X,Y;
			for(k=0;k<i;k++,w=w*wn)
			{
				X=x[k+j];Y=w*x[k+j+i];
				x[k+j]=X+Y;x[k+j+i]=X-Y;
			}
		}
	}
	if(f==-1) for(int i=0;i<n;i++) x[i].r/=n;
}
char s[N],a[N];
int n,m,sum,ans;
int mx,md,p[N];
void manc()
{
	for(int i=1;i<=n;i++)
	{
		a[i<<1]=s[i];
		a[i<<1|1]='#';
	}
	int nn=n+1<<1;a[0]='!';
	a[1]='#';a[nn]='&';
	for(int i=1;i<=nn;i++)
	{
		if(mx>=i) p[i]=min(mx-i,p[2*md-i]);
		else p[i]=1;
		while(a[i-p[i]]==a[i+p[i]]) p[i]++;
		if(i+p[i]>mx) mx=i+p[i],md=i;
	}
	for(int i=2;i<nn;i++) (sum+=p[i]>>1)%=mod;
}
int ksm(ll a,int b)
{
	ll sum=1;
	while(b)
	{
		if(b&1) sum=sum*a%mod;
		a=a*a%mod;b>>=1;
	}
	return sum;
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	manc();
	for(int i=0;i<n;i++)
	{
		if(s[i+1]=='a') A[i].r=1;
		else B[i].r=1;
	}
	for(m=1;m<(n<<1);m<<=1) L++;
	for(int i=0;i<m;i++) r[i]=r[i>>1]>>1|((i&1)<<L);
	FFT(A,m,1);FFT(B,m,1);
	for(int i=0;i<m;i++)
	{
		A[i]=A[i]*A[i];
		B[i]=B[i]*B[i];
	}
	FFT(A,m,-1);FFT(B,m,-1);
	for(int i=0,x;i<n+n-1;i++)
	{
		x=(int)(A[i].r+0.1)+(int)(B[i].r+0.1);
		x=x+1>>1;
		ans+=ksm(2,x)-1;
		ans%=mod;
	}
	printf("%d\n",(ans-sum+mod)%mod);
	return 0;
}