Description

略。见BZOJ3160

Solution

对于“不能是连续的一段”,可以先计算所有答案,然后减去连续一段的,即回文串,这个用回文自动机或者manacher可以得出
考虑以每个位置为中心的对称元素对个数f[i],那么i位置对答案的贡献是2^{f[i]}-1
如果把a视为1,b视为-1,然后把原串长度*4,卷积,那么以i为中心的元素对如果相同,则贡献1,否则贡献-1

Code

  1. #include<bits/stdc++.h>
  2. typedef double lf;
  3. #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
  4. #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
  5. inline int mod(int x,int y){if(x>=y)return x-y;return x;}
  6. #define N 524288
  7. struct num
  8. {
  9. lf r,i;
  10. num(){r=i=0;}
  11. num(lf x){r=x,i=0;}
  12. num(lf x,lf y){r=x,i=y;}
  13. num(const num &x){r=x.r,i=x.i;}
  14. inline num& operator +=(const num &x){r+=x.r,i+=x.i;}
  15. inline num& operator -=(const num &x){r-=x.r,i-=x.i;}
  16. 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;}
  17. inline num operator +(const num &x){num t=*this;t+=x;return t;}
  18. inline num operator -(const num &x){num t=*this;t-=x;return t;}
  19. inline num operator *(const num &x){num t=*this;t*=x;return t;}
  20. };
  21. int id[N];
  22. num tx[N],mf[N];
  23. inline void init_id(int y)
  24. {
  25. fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1;
  26. }
  27. #define idft(a,b) dft(a,b,1)
  28. inline void dft(num *s,int n,bool II=0)
  29. {
  30. fo0(i,1<<n)tx[i]=s[id[i]];
  31. fo1(p,n)
  32. {
  33. lf tmp=M_PI*2/(1<<p);
  34. if(II)tmp=-tmp;
  35. num t0(1),t1(cos(tmp),sin(tmp));
  36. fo0(i,1<<p-1)mf[i]=t0,t0*=t1;
  37. num X,Y;
  38. for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir)
  39. {
  40. X=tx[i|j],Y=tx[i|j|ir]*mf[j];
  41. tx[i|j]=X+Y,tx[i|j|ir]=X-Y;
  42. }
  43. }
  44. fo0(i,1<<n)s[i]=tx[i];
  45. }
  46. #define N2 100010
  47. struct node
  48. {
  49. int len,cnt;
  50. node *nxt[2],*fail;
  51. }t[N2+2],*tm=t+2;
  52. inline void build(char *s,int n)
  53. {
  54. t[0].len=0,t[1].len=-1;
  55. node *cur=t+1,*tmp,*t2;
  56. t[0].fail=t+1;
  57. for(int i=0;i<n;i++)
  58. {
  59. char u=s[i]-'a';
  60. for(;s[i]!=s[i-1-cur->len];cur=cur->fail);
  61. if(cur->nxt[u])
  62. cur=cur->nxt[u],cur->cnt++;
  63. else
  64. {
  65. tmp=cur->nxt[u]=tm++;
  66. tmp->len=cur->len+2;
  67. tmp->cnt=1;
  68. if(tmp->len==1)
  69. tmp->fail=t;
  70. else
  71. {
  72. for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail);
  73. tmp->fail=t2->nxt[u];
  74. }
  75. cur=tmp;
  76. }
  77. }
  78. }
  79. inline void count()
  80. {
  81. for(node *x=tm-1;x>=t;x--)
  82. if(x->fail)x->fail->cnt+=x->cnt;
  83. }
  84. #define P 1000000007
  85. inline int cnt()
  86. {
  87. int ans=0;
  88. for(node *x=tm-1;x>t+1;x--)
  89. ans=mod(ans+x->cnt,P);
  90. return ans;
  91. }
  92. char s[100000];
  93. num p[N];
  94. int po[100001];
  95. int main()
  96. {
  97. scanf("%s",s);
  98. int n=strlen(s);
  99. fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P);
  100. int y=0;
  101. while((1<<(y+1))<n*4)y++;y++;
  102. fo0(i,n)p[i]=s[i]=='a'?1:-1;
  103. init_id(y);
  104. dft(p,y);
  105. fo0(i,1<<y)p[i]*=p[i];
  106. idft(p,y);
  107. lf t=1.0/(1<<y);
  108. int ans=0;
  109. fo0(i,n*2-1)
  110. {
  111. int cnt=round(p[i].r*t);
  112. cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2;
  113. ans=mod(ans+po[cnt],P);
  114. }
  115. build(s,n);
  116. count();
  117. printf("%d",mod(ans+P-cnt(),P));
  118. }