(题目链接)

题意

　　给定一个由'a'和'b'构成的字符串，求不连续回文子序列的个数。

Solution

　　在膜拜了的题解后，我觉得有必要自己写一发，感觉这道题倒还是可以理解的。

　　不连续的回文子序列个数感觉并不是特别好求，而不连续的回文子序列个数=回文子序列个数-连续回文子序列个数。后者很好办，就是${Manacher}$板子，考虑没有任何限制的回文子序列个数怎么求。

　　借用${Manacher}$的做法，先在字符串中添加分隔符，对于一个串${S}$长成这样：${aba}$，我们添加分隔符，那么得到${S'}$：${\$\#a\#b\#a\#}$   

　　我们令${f_i}$表示以${i}$为中心的对称字符对的个数，那么很显然，以${i}$为中心的回文子序列的个数就等于${2^{f_i}-1}$，那么整个答案就等于：$${\sum_{i=1}^{2*n+1} {2^{f_i}-1}}$$

　　如果我们知道了${f_i}$，那么就可以算出答案了，而${f_i}$怎么求呢。

　　这里假设${S}$和${S'}$的下标都从${0}$开始（因为多项式的次数是从${0}$开始的，这样的话就可以避免一些下标的细节问题），如果${S'}$中的两个字母比如说这两个${a}$，它们是关于中间的${b}$对称的，想一想这两个${a}$与${b}$位置之间的关系：${S'_2=a,S'_6=a,S'_4=b}$，可以得到它们的下标：${x=2,y=6,mid=4}$，很显然：${x+y=2*mid}$。因为${S'}$中字母的下标都是偶数，我们将两边同时除以${2}$，得到这样一个式子：${x/2+y/2=mid}$。那么${x/2}$和${y/2}$表示什么呢，是不是就是${S'}$中的字母在原串${S}$中的位置${+1}$。那么我们可以得到这样一个结论：如果原串中两个字母${S_x=S_y}$，它们就会关于${S'_{(x+1)+(y+1)}}$对称。

　　那么我们就可以写出${f_i}$的表达式了：$${f_i=\lfloor{  \frac{1+\sum_{j=0}^{i-2} {[s_j=s_{i-2-j}]}}  {2}  }\rfloor }$$

　　这是一个卷积的形式，我们很容易想到用${FFT}$来解决这个东西。首先考虑${a}$对答案的贡献，令${a=1,b=0}$，求一遍${FFT}$；再考虑${b}$对答案的贡献，令${a=0,b=1}$，再求一遍${FFT}$；两者相加再加${1}$最后除以${2}$取下整就是${f}$了。代入之前的结论中即可出解。

　　话说我还是不会构造多项式，还是写一写吧。。比如说样例：${aba}$。我们考虑算${a}$的贡献：

$${A(x)=1*x^0+0*x^1+1*x^2}$$

$${B(x)=1*x^0+0*x^1+1*x^2}$$

　　那么最后的${f_i}$就是${A(x)*B(x)}$的第${i-1}$项的系数（次数为${i-2}$）。

细节

　　细节还是蛮多的，搞清楚下标始终是个问题。。注意数组大小，以及计算${f}$的时候要开LL。

代码

// bzoj3160#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define MOD 1000000007#define inf 1ll<<60#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;typedef complex
            
              E;const int maxn=400010;int bin[maxn],rev[maxn],f[maxn],p[maxn],n,L;E a[maxn],b[maxn];char s[maxn],st[maxn];void FFT(E *a,int f) { for (int i=0;i
             
              mx) mx=p[i]+i,id=i; tot=(tot+p[i]/2)%MOD; } return tot;}int main() { scanf("%s",s); int len=strlen(s); bin[0]=1;for (int i=1;i
              
               >1]>>1) | ((i&1)<<(L-1)); for (int i=0;i
               
                >1]-1)%MOD; printf("%lld",(ans+MOD-Manacher(s,len))%MOD); return 0;}