BZOJ 3160: 万径人踪灭 January 20, 2017 ###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1 ###Code ```c++ #include<bits/stdc++.h> typedef double lf; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) inline int mod(int x,int y){if(x>=y)return x-y;return x;} #define N 524288 struct num { lf r,i; num(){r=i=0;} num(lf x){r=x,i=0;} num(lf x,lf y){r=x,i=y;} num(const num &x){r=x.r,i=x.i;} inline num& operator +=(const num &x){r+=x.r,i+=x.i;} inline num& operator -=(const num &x){r-=x.r,i-=x.i;} inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;} inline num operator +(const num &x){num t=*this;t+=x;return t;} inline num operator -(const num &x){num t=*this;t-=x;return t;} inline num operator *(const num &x){num t=*this;t*=x;return t;} }; int id[N]; num tx[N],mf[N]; inline void init_id(int y) { fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1; } #define idft(a,b) dft(a,b,1) inline void dft(num *s,int n,bool II=0) { fo0(i,1<<n)tx[i]=s[id[i]]; fo1(p,n) { lf tmp=M_PI*2/(1<<p); if(II)tmp=-tmp; num t0(1),t1(cos(tmp),sin(tmp)); fo0(i,1<<p-1)mf[i]=t0,t0*=t1; num X,Y; for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir) { X=tx[i|j],Y=tx[i|j|ir]*mf[j]; tx[i|j]=X+Y,tx[i|j|ir]=X-Y; } } fo0(i,1<<n)s[i]=tx[i]; } #define N2 100010 struct node { int len,cnt; node *nxt[2],*fail; }t[N2+2],*tm=t+2; inline void build(char *s,int n) { t[0].len=0,t[1].len=-1; node *cur=t+1,*tmp,*t2; t[0].fail=t+1; for(int i=0;i<n;i++) { char u=s[i]-'a'; for(;s[i]!=s[i-1-cur->len];cur=cur->fail); if(cur->nxt[u]) cur=cur->nxt[u],cur->cnt++; else { tmp=cur->nxt[u]=tm++; tmp->len=cur->len+2; tmp->cnt=1; if(tmp->len==1) tmp->fail=t; else { for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail); tmp->fail=t2->nxt[u]; } cur=tmp; } } } inline void count() { for(node *x=tm-1;x>=t;x--) if(x->fail)x->fail->cnt+=x->cnt; } #define P 1000000007 inline int cnt() { int ans=0; for(node *x=tm-1;x>t+1;x--) ans=mod(ans+x->cnt,P); return ans; } char s[100000]; num p[N]; int po[100001]; int main() { scanf("%s",s); int n=strlen(s); fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P); int y=0; while((1<<(y+1))<n*4)y++;y++; fo0(i,n)p[i]=s[i]=='a'?1:-1; init_id(y); dft(p,y); fo0(i,1<<y)p[i]*=p[i]; idft(p,y); lf t=1.0/(1<<y); int ans=0; fo0(i,n*2-1) { int cnt=round(p[i].r*t); cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2; ans=mod(ans+po[cnt],P); } build(s,n); count(); printf("%d",mod(ans+P-cnt(),P)); } ``` [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=3160