题目大意：给一个字符串，求所有相邻两回文子串的外侧下标之积的和
题目分析：另L[i]为所有以 i 为右端点的回文字串的左端点之和，同理，另R[i]表示所有以 i 为左端点的回文子串的右端点之和。显然，答案为sigma(L[i]*R[i+1]) 其中，1<=i<length(字符串)。求出L和R是关键。先用manacher算法处理出p数组，然后再求出L和R。求L和R的思想（非常巧妙）跟树状数组求区间和的思想差不多。不过，这道题如果用树状数组或线段树的话会超时。
参考代码：
# include<iostream>
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
# define LL long long const int mod=1000000007;
const int N=1000000; char str[N+5];
char m[(N<<1)+5];
int p[(N<<1)+5]; LL addtag[2][N+5];
LL subtag[2][N+5];
LL addcnt[2][N+5];
LL subcnt[2][N+5];
LL val[2][N+5]; void manacher(char *ch)
{
int len=strlen(ch+1);
int cnt=0;
m[cnt++]='@';
m[cnt++]='#';
for(int i=1;i<=len;++i){
m[cnt++]=ch[i];
m[cnt++]='#';
}
m[cnt]='\0';
int id,mx=0;
for(int i=1;i<cnt;++i){
if(mx>i) p[i]=min(mx-i,p[2*id-i]);
else p[i]=1;
while(m[i-p[i]]==m[i+p[i]]) ++p[i];
if(i+p[i]>mx){
mx=i+p[i];
id=i;
}
}
} void update(int id,int l,int r,int a)
{
addtag[id][l]+=a;
addtag[id][l]%=mod;
++addcnt[id][l];
subtag[id][r+1]+=a-r+l;
subtag[id][r+1]%=mod;
++subcnt[id][r];
} void pushDown(int n)
{
for(int i=1;i<=n;++i){
if(addcnt[0][i]){
val[0][i]+=addtag[0][i];
val[0][i]%=mod;
addtag[0][i+1]+=addtag[0][i]-addcnt[0][i];
addtag[0][i+1]%=mod;
addcnt[0][i+1]+=addcnt[0][i];
}
if(subcnt[0][i]){
val[0][i]-=subtag[0][i];
val[0][i]%=mod;
subtag[0][i+1]+=subtag[0][i]-subcnt[0][i];
subtag[0][i+1]%=mod;
subcnt[0][i+1]+=subcnt[0][i];
}
if(addcnt[1][i]){
val[1][i]+=addtag[1][i];
val[1][i]%=mod;
addtag[1][i+1]+=addtag[1][i]-addcnt[1][i];
addtag[1][i+1]%=mod;
addcnt[1][i+1]+=addcnt[1][i];
}
if(subcnt[1][i]){
val[1][i]-=subtag[1][i];
val[1][i]%=mod;
subtag[1][i+1]+=subtag[1][i]-subcnt[1][i];
subtag[1][i+1]%=mod;
subcnt[1][i+1]+=subcnt[1][i];
}
}
} int main()
{
while(~scanf("%s",str+1))
{
manacher(str);
memset(val,0,sizeof(val));
memset(addtag,0,sizeof(addtag));
memset(subtag,0,sizeof(subtag));
memset(addcnt,0,sizeof(addcnt));
memset(subcnt,0,sizeof(subcnt));
for(int i=1;m[i];++i){
if(i&1){
if(p[i]==1) continue;
update(0,i/2+1,i/2+p[i]/2,i/2);
update(1,i/2-p[i]/2+1,i/2,i/2+p[i]/2);
}else{
int id=i/2;
int l=(p[i]-1)/2;
update(0,id,id+l,id);
update(1,id-l,id,id+l);
}
}
int n=strlen(str+1);
pushDown(n);
LL ans=0;
for(int i=1;i<n;++i){
ans+=val[0][i]*val[1][i+1];
ans%=mod;
}
while(ans<0) ans+=mod;
printf("%lld\n",ans);
}
return 0;
}