题意：给你一个串，若里面有两个相邻的没有交集的回文串的话，设为S[i...j] 和 S[j+1...k]，对答案的贡献是i*k，就是左端点的值乘上右端点的值。
首先，如果s[x1....j]、s[x2....j]、s[x3....j]....s[xn....j]、是回文串，而且s[j+1...y1]、s[j+1...y2]、s[j+1...y3]、也是回文串，那么这些串对答案的贡献一共就是(x1+x2+...+xn)*(y1+y2+....+yn)
所以想到了用cntL[i]表示：以i这个字符为结尾的回文串的左端点之和，cntR[i]表示：以i这个字符为开始的回文串的右端点之和。
所以答案就是for i=1 to lenstr-1 ans += cntL[i]*cntR[i+1];
通俗点说吧，根据manacher，p[i]就表示以i这个字符为中心的回文串的半径长度，所以有s[i-p[i]...i+p[i]]是一个回文串
所以cntL[i+p[i]]就要加上i-p[i]，然后因为s[i-p[i]+1...i+p[i]-1]也是一个回文串，所以cntL[i+p[i]-1]就要加上i-p[i]+1等等之类的。所以就是在[i..i+p[i]]这个区间上，依次加上 i、i-1、i-2、.....i-p[i]，这样一个公差为-1的等差数列。这个可以用延迟标记来做
先看简单的，在[L,R]上加上一个数val，我们只需要cnt[L] += val; cnt[R+1] -= val; 然后O(n)扫描，即可得到这个数组的所有值。但是现在是等差数列呢？其实是差不多的，只不过要开多一个数组而已。
首先，如果是在[begin,end]上加上一个以val为首相的等差数列，可以这样考虑。首先cnt[begin] += val;然后可以算出结束的时候的值是多少把？cnt[end+1] -= calc_end_val;即可。然后中间的公差，因为可能有叠加现象，我们要开多个数组subL[i]表示这个位置有多少个-1，这个subL[i]就像一开始的最简单的这样传递下去即可。就是subL[begin] += 1; subL[end+1] -= 1;
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include<stack>
#include <string>
const int maxn = +;
const int MOD = ;
int cntL[maxn],cntR[maxn];
int subL[maxn],subR[maxn];
char str[maxn<<];
int p[maxn<<];
void addL (int begin,int end,int val)
{
if (end<begin) return ;
cntL[begin] += val;
cntL[end+] -= begin-end+val;
subL[begin+]++;
subL[end+]--; cntL[begin] %= MOD;
cntL[end+] = (cntL[end+]+MOD)%MOD;
subL[begin+]%=MOD;
subL[end+]=(subL[end+]+MOD)%MOD;
return ;
}
void addR (int begin,int end,int val)
{
if (end<begin) return ;
cntR[begin] += val;
cntR[end+] -= begin-end+val;
subR[begin+]++;//记录有多少个数列覆盖的，记录公差
subR[end+]--; cntR[begin] %= MOD;
cntR[end+] = (cntR[end+]+MOD)%MOD;
subR[begin+]%=MOD;
subR[end+]=(subR[end+]+MOD)%MOD;
return ;
}
int manacher (char str[],int lenstr)
{
str[]='*';
for (int i=lenstr;i>=;i--)
{
str[i+i+]=str[i+];
str[i+i+]='#';
}
int id=,maxlen=;
for (int i=;i<=*lenstr+;i++)
{
if (p[id]+id>i)
{
p[i]=min(p[id]+id-i,p[*id-i]);
}
else p[i]=;
while (str[i+p[i]] == str[i-p[i]]) ++p[i];
if (p[id]+id<p[i]+i) id=i;
maxlen=max(maxlen,p[i]);
}
return maxlen-;
} void init_arr(int gg)
{
for (int i=;i<=gg;++i)
{
subL[i] += subL[i-];
cntL[i] += cntL[i-]-subL[i]; subR[i] += subR[i-];
cntR[i] += cntR[i-]-subR[i]; subL[i] %= MOD; subR[i] %= MOD;
cntL[i]=(cntL[i]+MOD)%MOD; cntR[i]=(cntR[i]+MOD)%MOD;
}
return ;
}
void init ()
{
memset(cntL,,sizeof cntL); memset(cntR,,sizeof cntR);
memset(subL,,sizeof subL); memset(subR,,sizeof subR);
return ;
}
void work ()
{
init();
int lenstr = strlen(str+);
manacher(str,lenstr);
for (int i=;i<=*lenstr+;++i)
{
int len = p[i]-;
if (len==) continue;
if (i&) //'#'所在位置
{
int pos = i/;//截断
//len必须是偶数
int t = len/;
int begin = pos-t+; //这些细节要慢慢算啦，慢慢推公式
int end = t+pos;
addL(pos+,end,pos);
addR(begin,pos,end);
}
else //字母所在位置
{
int pos = i/;
len--;
len/=;
int begin = pos-len;
int end = pos+len;
addL(pos,end,pos);
addR(begin,pos,end);
}
}
init_arr(lenstr);
LL ans = ;
for (int i=;i<=lenstr-;++i)
{
ans += 1LL*cntL[i]*cntR[i+];
ans %= MOD;
}
printf ("%I64d\n",ans);
return ;
}
int main ()
{
#ifdef local
freopen("data.txt","r",stdin);
#endif
while(scanf("%s",str+)!=EOF) work();
return ;
}