建回文树。
正反建统计一种前缀和求出所有不相交的，用总数减去就是答案数。
在这里我们可以知道一个字符串中所有回文串的个数即为num数组之和（因为以一个节点为回文串结尾的字串都是唯一的）
也可以是cnt数组的和（想想看为什么）
题目链接：http://www.tsinsen.com/ViewGProblem.page?gpid=A1393
来源是Codeforces17E，但这样会MLE所以可以使用Vector替代next数组（时间换空间）这里不给出代码。
By:大奕哥
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+;
const int mod=;
const int M=;
struct node
{
int num[N],cnt[N],nex[N][M],fail[N],S[N],len[N];
int n,p,last;
int newnode(int l)
{
for(int i=;i<M;++i)nex[p][i]=;
cnt[p]=num[p]=;
len[p]=l;
return p++;
}
void init()
{
p=;n=;
newnode();newnode(-);
last=n=;
S[n]=-;fail[]=;
}
int getfail(int x)
{
while(S[n-len[x]-]!=S[n])x=fail[x];
return x;
}
int add(int c)
{
c=c-'a';
S[++n]=c;
int cur=getfail(last);
if(!nex[cur][c])
{
int now=newnode(len[cur]+);
fail[now]=nex[getfail(fail[cur])][c];
nex[cur][c]=now;
num[now]=num[fail[now]]+;
}
last=nex[cur][c];
cnt[last]++;
return num[last];
}
void count()
{
for(int i=p-;i>=;--i)cnt[fail[i]]+=cnt[i];
}
}T;
char s[N];
int ll[N],rr[N];
int main()
{
int n;long long sum=,ans=;
scanf("%d%s",&n,s);
T.init();
for(int i=n-;i>=;--i)
{
ll[i]=(T.add(s[i])+ll[i+])%mod;
}
T.init();
for(int i=;i<n;++i)
{
rr[i]=T.add(s[i]);sum+=rr[i];sum%=mod;
ans=(ans+1ll*ll[i+]*rr[i]%mod)%mod;
}
ans=(1ll*sum*(sum-)/%mod-ans+mod)%mod;
printf("%lld\n",ans);
return ;
}
Ps:随时注意取模。。。