万径人踪灭 bzoj-3160

题目大意：给定一个ab串。求所有的子序列满足：位置和字符都关于某条对称轴对称而且不连续。

注释：$1\le n\le 10^5$。

想法：

看了大爷的题解，OrzOrz。

因为对称轴可以是两个字符中间的位置，所以我们把字符串按照$Manacher$的形式倍增。

我们希望处理出一个数组$f$，$f_i$表示以$i$为对称轴的左右相等字符个数。

以当前位置为对称轴的答案显然就是$2^{f_i}-1$。

因为还有不连续的条件，我们只需要减掉$Manacher$的回文半径即可。

现在考虑如何能求出$f$数组。

不难发现：其实原序列中的第$i$个字符如果和第$j$个字符相等那么会更新到倍增序列后的第$i+j$个字符。

所以$f_i=((\sum\limits_{j=0}^{i-1} (s[j]==s[i-j]))+1)/2$。

看起来像卷积的形式，想到$FFT$。

但是$FFT$只能做乘法，这个题怎么办？

我们先把所有的$a$字符都变成$1$，$b$字符变成$0$，然后统计$((\sum\limits_{j=0}^{i-1} a[j]\cdot a[i-j])+1)/2$。

再把所有的$b$字符变成$1$，$a$字符变成$0$。

用$FFT$优化卷积即可。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define mod 1000000007 #define N 100010 using namespace std;typedef long long ll;typedef double db;const db pi=acos(-1);struct cp{	db x,y;	cp() {x=y=0;}	cp(db x_,db y_){x=x_,y=y_;}	cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}	cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}	cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}}a[N<<2];void fft(cp *a,int len,int flg){	int i,j,k,t;	cp w,wn,tmp;	for(i=k=0;i
          
           k) swap(a[i],a[k]); for(j=len>>1;(k^=j)
           
            >=1); } for(k=2;k<=len;k<<=1) { t=k>>1; wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k)); for(i=0;i
            
             1;f[i]++) if(t[i+f[i]+1]!=t[i-f[i]-1]) break; if(i+f[i]>now+f[now]) now=i; ans-=(f[i]+1)>>1; ans%=mod; }}int main(){ scanf("%s",s); n=strlen(s); int len=1; while(len<(n<<1))len<<=1; for(int i=0;i
             
              >1]-1)%mod; printf("%d\n",(ans+mod)%mod); return 0;}