BZOJ3160 万径人踪灭

对于每个可以作为对称轴的位置，我们算出以其为对称轴有多少对位置和字符是对称的，设为t[i]，若不考虑不能连续，则我们可以从这t[i]对里任选出来任意对，都是可行的答案，且不重不漏，所以不考虑不能连续的情况的答案为sigma 2^t[i]-1，考虑不能是连续子串，再减去回文子串的数量即可

回文子串数量manacher求就可以了

考虑一下，如果两个位置和字符a[i]和a[j]关于第x个位置对称，那么就是i+j==2*x并且a[i]==a[j]，如果a[i]和a[j]关于x与x+1中间的夹缝对称，那么就有i+j==2*x+1并且a[i]==a[j]（其实随便YY一下就会觉得这是一个卷积，把串复制一遍放上边，对称的两个点上下之间连线，然后就能直接看出来是卷积）

明显是一个卷积的形式，由于只有a和b两种字符，对于a和b分开来计算，先让所有为a的位置为1，其余为0算一遍卷积，再让所有为b的位置为1，算一遍卷积，两遍卷积的结果加起来就得到了t数组，然后就能算答案了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<ctime>
#include<vector>
#include<stack>
#include<set>
#include<bitset>
#include<map>
#include<queue>
using namespace std;
#define MAXN 400010
#define MAXM 1010
#define MOD 1000000007
#define INF 1000000000
#define eps 1e-8
#define ll long long
const double pi=acos(-1);
struct cl{
	double x;
	double y;
	cl(){
		
	}
	cl(double _x,double _y){
		x=_x;
		y=_y;
	}
	friend cl operator +(cl x,cl y){
		return cl(x.x+y.x,x.y+y.y);
	}
	friend cl operator -(cl x,cl y){
		return cl(x.x-y.x,x.y-y.y);
	}
	friend cl operator *(cl x,cl y){
		return cl(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);
	}
	friend cl operator /(cl x,double y){
		return cl(x.x/y,x.y/y);
	}
};
int n;
char s[MAXN];
int a[MAXN];
int f[MAXN],now,mx; 
int ans;
cl b[MAXN];
int L,R[MAXN];
ll t[MAXN];
void fft(cl *a,int f){
	int i,j,k;
	for(i=0;i<n;i++){
		if(i<R[i]){
			swap(a[i],a[R[i]]);
		}
	}
	for(i=1;i<n;i<<=1){
		cl wn(cos(pi/i),f*sin(pi/i));
		for(j=0;j<n;j+=(i<<1)){
			cl w(1,0);
			for(k=0;k<i;k++,w=w*wn){
				cl x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;
				a[j+k+i]=x-y;
			}
		}
	}
	if(f==-1){
		for(i=0;i<n;i++){
			a[i]=a[i]/n;
		}
	}
}
ll mi(ll x,ll y){
	ll re=1;
	while(y){
		if(y&1){
			(re*=x)%=MOD;
		}
		(x*=x)%=MOD;
		y>>=1;
	}
	return re;
}
int main(){
	int i;
	scanf("%s",s+1);
	n=strlen(s+1);
	for(i=n;i;i--){
		s[i<<1]=s[i];
		s[i<<1|1]='*';
		if(s[i]=='a'){
			a[i]=1;
		}else{
			a[i]=2;
		}
	}
	s[0]='$';
	s[1]='*';
	int N=n<<1|1;
	for(i=1;i<=N;i++){
		if(i<=mx){
			f[i]=min(f[now*2-i],mx-i);
		}else{
			f[i]=0;
		}
		for(;s[i-f[i]-1]==s[i+f[i]+1];f[i]++){
			
		}
		if(i+f[i]>mx){
			mx=i+f[i];
			now=i;
		}
	}
	for(i=1;i<=N;i++){
		((ans+=MOD-(f[i]+1)/2))%=MOD;
	}
	N=n<<1;
	for(n=1;n<=N;n<<=1){
		L++;
	}
	for(i=0;i<n;i++){
		R[i]=R[i>>1]>>1|((i&1)<<(L-1));
	}
	for(i=0;i<n;i++){
		b[i].x=(a[i]==1);
		b[i].y=0;
	}
	fft(b,1);
	for(i=0;i<n;i++){
		b[i]=b[i]*b[i];
	}
	fft(b,-1);
	for(i=0;i<n;i++){
		t[i]+=b[i].x+0.1;
	}
	for(i=0;i<n;i++){
		b[i].x=(a[i]==2);
		b[i].y=0;
	}
	fft(b,1);
	for(i=0;i<n;i++){
		b[i]=b[i]*b[i];
	}
	fft(b,-1);
	for(i=0;i<n;i++){
		t[i]+=b[i].x+0.1;
		t[i]=(t[i]+1)/2;
		(ans+=mi(2,t[i])-1)%=MOD;
	}
	printf("%d\n",ans);
	return 0;
}

/*
abaabaa
*/