题目链接：bzoj3160 题目大意： 给一个仅含’a’、’b’两种字符的长度为n的串，问 字母对称(即回文)且位置也对称，且不连续的子序列(可以含某段是连续的但总的要不连续)有多少个。 如果看不懂↑，看题目里的栗子吧
题解： FFT+manacher hyc太强辣%%% 首先，要求位置对称的话，那么每对的下标和恒为定值。 就是对于一个满足条件的子序列来说，设它的对称轴为k。有 s[k−i]=s[k+i] 。 于是卷积形式就出来了 设F(k)表示以k为对称轴的满足s[k+i]=s[k-i]的对数有多少个。 即 F(k)=∑[s[k+i]==s[k−i]] 设个数组a[i]=(s[i]==’a’) 那么 F(k)=∑a[k+i]×a[k−i] 反过来问b的也做一次。
最后的答案= ∑2nk=02F(k) -空串-回文子串。 就是算出多少对之后，枚举这一对选还是不选。有可能全都不选那么就构成了空串，也有可能构成了回文子串不满足条件，那么这些都要减掉。求回文子串的个数就用Manacher就好了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; #define maxn 400010 const double pi=acos(-1); const LL mod=1000000007; struct Complex { double x,y; Complex(){x=y=0;} Complex(double x,double y):x(x),y(y){} friend inline Complex operator + (Complex x,Complex y){return Complex(x.x+y.x,x.y+y.y);} friend inline Complex operator - (Complex x,Complex y){return Complex(x.x-y.x,x.y-y.y);} friend inline Complex operator * (Complex x,Complex y){return Complex(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);} }; char s[maxn];Complex a[maxn]; int mymin(int x,int y){return (x<y)?x:y;} void DFT(Complex *c,int ln,int t) { for (int i=0,j=0;i<ln;i++) { if (i>j) swap(c[i],c[j]); for (int l=ln>>1;(j^=l)<l;l>>=1); } for (int s=1;(1<<s)<=ln;s++) { int m=(1<<s); Complex wn(cos(2*pi/m),t*sin(2*pi/m)); for (int k=0;k<ln;k+=m) { Complex w(1,0); for (int j=0;j<(m>>1);j++,w=w*wn) { Complex a0=c[j+k]; Complex a1=w*c[j+k+(m>>1)]; c[j+k]=a0+a1; c[j+k+(m>>1)]=a0-a1; } } } } LL ans[maxn]; void FFT(int ln,Complex *c) { int i,fn=1;while (fn<=ln*2) fn<<=1; DFT(c,fn,1); for (int i=0;i<=fn;i++) c[i]=c[i]*c[i]; DFT(c,fn,-1); for (int i=0;i<=fn;i++) { LL tt=(LL)(c[i].x/fn+0.5); ans[i]=(tt%mod+ans[i])%mod; c[i].x=c[i].y=0; } } char ss[maxn*2];int g[maxn]; LL manacher(int n) { int i,m=0;ss[m]='#'; for (i=0;i<=n;i++) { ss[++m]=s[i]; ss[++m]='#'; } int mx=0,id=0; for (i=1;i<=m;i++) { if (i>mx) g[i]=1; else g[i]=mymin(mx-i,g[2*id-i]); while (i-g[i]>=0 && i+g[i]<=m && ss[i+g[i]]==ss[i-g[i]]) g[i]++; if (i+g[i]-1>mx) {mx=i+g[i]-1;id=i;} } LL ret=0; for (i=0;i<=m;i+=2) ret=(ret+(LL)g[i]/2)%mod; for (i=1;i<=m;i+=2) ret=(ret+(LL)(g[i]+1)/2)%mod; return ret; } LL bit[maxn]; int main() { //freopen("a.in","r",stdin); //freopen("a.out","w",stdout); int n,i; gets(s);n=strlen(s);n--; memset(ans,0,sizeof(ans)); for (i=0;i<=n;i++) a[i].x=(s[i]=='a'); FFT(n,a); for (i=0;i<=n;i++) a[i].x=(s[i]=='b'); FFT(n,a); for(i=0;i<=n+n;i++) ans[i]=(ans[i]+1)/2;//每一对会被算两次 LL sum=0;bit[0]=1; for (i=1;i<=n+n;i++) bit[i]=(bit[i-1]<<1)%mod; for (i=0;i<=n+n;i++) sum=(sum+bit[ans[i]])%mod; sum=sum-(2*n+1)-manacher(n); sum=(sum%mod+mod)%mod; printf("%lld\n",sum); return 0; }