BZOJ3160:万径人踪灭

FFT+Manacher.

不连续只需要减去连续的就可以了,连续的可以直接Manacher算出来.

其他全部对称的回文子序列就可以用生成函数那样FFT搞出来,把ab分开考虑就行.

有挺多细节的...包括下标运算什么什么的...

/**************************************************************
Problem: 3160
User: BeiYu
Language: C++
Result: Accepted
Time:3868 ms
Memory:29616 kb
****************************************************************/
#include bits/stdc++.h
using namespace std;
#define mpr make_pair
#define rr first
#define ii second
typedef pair double,double Complex;
typedef long long LL;
const int N = 5e5+50;
const long long p = 1e9+7;
const double Pi = M_PI;
Complex operator + (const Complex a,const Complex b) {
return mpr(a.rr+b.rr,a.ii+b.ii);
}
Complex operator - (const Complex a,const Complex b) {
return mpr(a.rr-b.rr,a.ii-b.ii);
}
Complex operator * (const Complex a,const Complex b) {
return mpr(a.rr*b.rr-a.ii*b.ii,a.rr*b.ii+a.ii*b.rr);
int n,l;
LL ans;
int f[N],g[N];
char t[N],s[N];
Complex a[N],b[N],c[N];
LL Pow(LL a,LL b,LL r=1) { for(;b;b =1,a=a*a%p) if(b 1) r=r*a%p;return r; }
void Manacher(char *t) {
int ll=0;
for(int i=0;i i++) s[ll++]='#',s[ll++]=t[i];
s[0]='$',s[ll++]='@';
for(int i=0,j=0,mx=0;i i++) {
if(mx i) f[i]=min(mx-i,f[j*2-i]);else f[i]=1;
while(i+f[i] ll i-f[i] =0 s[i+f[i]]==s[i-f[i]]) f[i]++;
if(i+f[i] mx) mx=i+f[i],j=i;
}
void init(int x) {
for(n=1;n n =1);n =1;
}
void Rev(Complex a[]) {
for(int i=0,j=0;i i++) {
if(i j) swap(a[i],a[j]);
for(int k=n 1;(j^=k) k =1);
}
}
void DFT(Complex a[],int r=1) {
Rev(a);
for(int i=2;i i =1) {
Complex wi=mpr(cos(2.0*Pi/i),r*sin(2.0*Pi/i));
for(int k=0;k k+=i) {
Complex w=mpr(1.0,0.0);
for(int j=k;j k+i/2;j++) {
Complex t1=a[j],t2=w*a[j+i/2];
a[j]=t1+t2,a[j+i/2]=t1-t2;
w=w*wi;
}
}
}
if(r==-1) for(int i=0;i i++) a[i].rr/=n;
}
void FFT(Complex a[],Complex b[],Complex c[]) {
DFT(a),DFT(b);
for(int i=0;i i++) c[i]=a[i]*b[i];
DFT(c,-1);
int main() {
scanf("%s",t);
l=strlen(t);
init(l);
for(int i=0;i i++) a[i]=mpr(t[i]=='a',0),b[i]=a[i];
// reverse(b,b+l);
// for(int i=0;i i++) cout (int)a[i].rr " ";cout endl;
// for(int i=0;i i++) cout (int)b[i].rr " ";cout endl;
FFT(a,b,c);
for(int i=0;i i++) g[i]=(int)(c[i].rr+0.5);
// for(int i=0;i i++) cout (int)(c[i].rr+0.5) " ";cout endl;
memset(a,0,sizeof(a)),memset(b,0,sizeof(b));
for(int i=0;i i++) a[i]=mpr(t[i]=='b',0),b[i]=a[i];
// reverse(b,b+l);
// for(int i=0;i i++) cout (int)a[i].rr " ";cout endl;
// for(int i=0;i i++) cout (int)b[i].rr " ";cout endl;
FFT(a,b,c);
for(int i=0;i i++) g[i]+=(c[i].rr+0.5);
// for(int i=0;i i++) cout (int)(c[i].rr+0.5) " ";cout endl;
for(int i=0;i i++) g[i]=(g[i]+1)/2;
// for(int i=0;i i++) cout g[i] " ";cout endl;
Manacher(t);
// for(int i=0;i i++) cout f[i] " ";cout endl;
for(int i=0;i l*2+1;i++) if(!(i 1)) f[i]-=1;
// for(int i=0;i i++) cout f[i] " ";cout endl;
for(int i=0;i l*2-1;i++) ans=(ans+Pow(2,g[i])-(f[i+1]+1)/2-1)%p;
cout ans endl;
return 0;
}
/*
abaabaa
#bbb#
##aa
53