C++14(g++5.4) 解法, 执行用时: 359ms, 内存消耗: 247132K, 提交时间: 2019-05-29 23:46:17

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#define PER(i,a,n) for(int i=n;i>=a;--i)
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;
typedef long long ll;
const int N = 2e6+10, P = 1e9+7;
int n, m, tot, cnt, last, fac[N];
int fail[N], len[N], ch[N][26], num[N];
ll sum[N];
char s[N], ss[N];

int getfail(int x) {
	while (ss[cnt-len[x]-1]!=ss[cnt]) x=fail[x];
	return x;
}
int insert(int c) {
	ss[++cnt] = c;
	int p = getfail(last);
	if (!ch[p][c]) {
		len[++tot] = len[p]+2;
		fail[tot]=ch[getfail(fail[p])][c];
		ch[p][c]=tot;
		num[tot]=num[fail[tot]]+1;
	}
	last = ch[p][c];
	return num[last];
}
void clear() {
	REP(i,0,tot) {
		memset(ch[i],0,sizeof ch[0]);
		num[i]=len[i]=fail[i]=0;
	}
	ss[0]='#',fail[0]=1,last=0;
	len[0]=0,len[1]=-1,tot=1,cnt=0;
}

int main() {
	scanf("%d%s", &n, s+1);
	clear();
	REP(i,1,n) { 
		s[i]-='a';
		sum[i] = (sum[i-1]+insert(s[i]))%P;
	}
	clear();
	ll ans = 0;
	PER(i,1,n) (ans += (ll)sum[i-1]*insert(s[i])) %= P;
	ans = (sum[n]*(sum[n]-1)%P*((P+1)/2)%P-ans)%P;
	if (ans<0) ans += P;
	printf("%lld\n", ans);
}

C++11(clang++ 3.9) 解法, 执行用时: 476ms, 内存消耗: 38140K, 提交时间: 2017-12-15 20:10:13

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4100000,P=1000000007;
int n,m,i,r,p,f[N],g[N],v[N];char a[N],s[N];
long long tot,ans;
void work(){
  for(i=1;i<=n;i++)s[i<<1]=a[i],s[i<<1|1]='#';
  s[0]='$',s[1]='#',s[m=(n+1)<<1]='@';
  for(r=p=0,f[1]=1,i=2;i<m;i++){
    for(f[i]=r>i?min(r-i,f[p*2-i]):1;s[i-f[i]]==s[i+f[i]];f[i]++);
    if(i+f[i]>r)r=i+f[i],p=i;
  }
  for(i=0;i<=n+5;i++)v[i]=0;
  for(i=2;i<=n*2;i++)v[(i+1)/2]++,v[(i+f[i])/2]--;
  for(i=1;i<=n+5;i++)v[i]=(v[i-1]+v[i])%P;
}
int main(){
  scanf("%d%s",&n,a+1);
  work();
  for(i=0;i<=n+5;i++)g[i]=v[i];
  reverse(g+1,g+n+1);
  reverse(a+1,a+n+1);
  work();
  for(i=1;i<=n;i++)(tot+=v[i])%=P;
  ans=tot*(tot-1)%P;
  ans=ans*(P+1)/2%P;
  for(i=1;i<=n;i++)v[i]=(v[i-1]+v[i])%P;
  for(i=2;i<=n;i++)ans=(ans-1LL*v[i-1]*g[i])%P;
  printf("%lld",(ans%P+P)%P);
}