寻找三元组(i,j,k)，使得(i,j)(j,k)都是回文字串，其中i<=j<k.

可以发现，对于每一位i,只要预处理出来有多少个以i为右端的回文串和以i为左端的回文串。把那些串的另一端的坐标和计算出来就可以了。

然后ans = ∑cntR[i]*cntL[i+1]

这里cntR[i]记录以i为右端的回文串的左端坐标和。cntL[i]同理。

然后这道题的数据范围是1e6，多case。必须要O(n)才能过。

首先用O(n)的Manacher处理每一位的回文半径，之后遍历处理

可以发现这里需要O(n)复杂度给指定区间加上一个等差序列。于是开几个数组维护，空间换时间。

用cnt_add记录加了多少次，add记录首项加了多少，这样从首项往后递推，每次add[i+1] = add[i]-cnt_add[i] cnt_add[i+1] += cnt_add[i] cntL[i] += add[i]

这样可以从首项更新到字符串尾。但是我们要更新一段值，就有一段多加了，于是就再开一个mns记录多加的的值.

比如要更新[l,r] 那么就给mns[r+1]置为add[r+1]时的值。这样就可以把多加的抵消了。同时也要维护一个cnt_mns记录次数。

最后还要注意分回文长度奇偶讨论。

//坑了好久的题。最开始想到了用树状数组维护cnt,成段更新，然而卡log。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5   6 #define LL long long  7 #define lson rt<<1,l,mid  8 #define rson rt<<1|1,mid+1,r  9 #define root 1,N,1 10 using namespace std; 11  12 const int maxn = 1e6+100; 13 const LL MOD = 1e9+7; 14  15 char Ma[2*maxn]; 16 int Mp[2*maxn]; 17 void update(LL &x,LL d) 18 { 19     x += d; 20     if(x >= MOD) x -= MOD; 21     if(x < 0) x += MOD; 22 } 23  24 void Manacher(char s[],int len) 25 { 26     memset(Mp,0,sizeof Mp); 27     int l = 0; 28     Ma[l++] = '$'; 29     Ma[l++] = '#'; 30     for(int i=0;i
         
           i ? min(Mp[2*id-i],mx-i) : 1; 40         while(Ma[i+Mp[i]] == Ma[i-Mp[i]] ) Mp[i]++; 41         if(i + Mp[i] > mx) 42         { 43             mx = i+Mp[i]; 44             id = i; 45         } 46     } 47 } 48  49 char line[maxn]; 50 int p[maxn]; 51 LL cntL[maxn],cntR[maxn]; 52 LL add[maxn],mns[maxn]; 53 LL cnt_add[maxn],cnt_mns[maxn]; 54  55 void init() 56 { 57     memset(cnt_mns,0,sizeof cnt_mns); 58     memset(cnt_add,0,sizeof cnt_add); 59     memset(add,0,sizeof add); 60     memset(mns,0,sizeof mns); 61 } 62  63 LL ans = 0; 64 void solve(int len) 65 { 66     init(); 67     for(int i=2;i<2*len+1;i++) 68     { 69         int tmp = Mp[i]; 70         if(Ma[i] == '#') 71         { 72             int cur = i/2+1,L = (i-tmp)/2+1, R = (i+tmp)/2-1,r = (tmp-1)/2; 73             update(add[L],R); 74             update(mns[cur],R-r); 75             cnt_add[L] ++; 76             cnt_mns[cur]++; 77         }else 78         { 79             int cur = i/2,L = (i-tmp)/2+1, R = (i+tmp)/2-1,r = 1+(tmp-1)/2; 80             update(add[L],R); 81             update(mns[cur+1],R-r); 82             cnt_add[L] ++; 83             cnt_mns[cur+1]++; 84         } 85     } 86     for(int i=1;i<=len;i++) 87     { 88         update(cntL[i],add[i]-mns[i]); 89         update(add[i+1],add[i]-cnt_add[i]); 90         update(mns[i+1],mns[i]-cnt_mns[i]); 91         update(cnt_add[i+1],cnt_add[i]); 92         update(cnt_mns[i+1],cnt_mns[i]); 93     } 94  95     init(); 96     for(int i=2;i<2*len+1;i++) 97     { 98         int tmp = Mp[i]; 99         if(Ma[i] == '#')100         {101             int cur = i/2+1,L = (i-tmp)/2+1, R = (i+tmp)/2-1,r = (tmp-1)/2;102             add[cur] += cur-1;103             mns[R+1] += cur - r - 1;104             cnt_add[cur] ++;105             cnt_mns[R+1] ++;106         }else107         {108             int cur = i/2,L = (i-tmp)/2+1, R = (i+tmp)/2-1,r = 1+(tmp-1)/2;109             add[cur] += cur;110             mns[R+1] += cur-r;111             cnt_add[cur] ++;112             cnt_mns[R+1] ++;113         }114     }115     for(int i=1;i<=len;i++)116     {117         update(cntR[i],add[i]-mns[i]);118         update(add[i+1],add[i]-cnt_add[i]);119         update(mns[i+1],mns[i]-cnt_mns[i]);120         update(cnt_add[i+1],cnt_add[i]);121         update(cnt_mns[i+1],cnt_mns[i]);122     }123     ans = 0;124     for(int i=1;i<=len;i++)125     {126         update(ans,(cntR[i]*cntL[i+1])%MOD);127     }128 }129 130 int main()131 {132     //freopen("1005.in","r",stdin);133     while(true)134     {135         char c;136         int len = 0;137         while((c = getchar()) && isalpha(c))138         {139             line[len++] = c;140         }141         if(c == EOF) break;142         Manacher(line,len);143 144         memset(cntL,0,sizeof cntL);145         memset(cntR,0,sizeof cntR);146         solve(len);147         printf("%I64d\n",(ans+MOD) % MOD);148     }149 }