记录编号	294074	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]优秀的拆分	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	6.521 s
提交时间	2016-08-11 16:50:46	内存使用	74.75 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=120010;
struct SAM{
	char s[N];
	int fa[N],pos[N],sa[N],rank[N];
	int son[N][26],end[N],rht[N],lcp[N];
	int ch[N][26],len[N],id[N],tot;
	int od[N],wv[N],lst,cnt;
	int mm[N],Min[N][25];
	void Init(){
		memset(s,0,sizeof(s)); 
		memset(ch,0,sizeof(ch));
		memset(end,0,sizeof(end));
		memset(son,0,sizeof(son));
		memset(pos,0,sizeof(pos));
		lst=cnt=1;tot=0;
	}

	void Insert(int c){
		int p=lst,np=lst=++cnt;end[lst]=1;
		id[len[np]=len[p]+1]=np;rht[np]=1;
		while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];
		if(!p)fa[np]=1;
		else{
			int q=ch[p][c],nq;
			if(len[q]==len[p]+1)fa[np]=q;
			else{
				len[nq=++cnt]=len[p]+1;
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				memcpy(ch[nq],ch[q],sizeof(ch[q]));
				while(ch[p][c]==q)ch[p][c]=nq,p=fa[p];
			}
		}
	}

	void Get_Right(){
		for(int i=1;i<=cnt;i++)wv[len[i]]++;
		for(int i=1;i<=cnt;i++)wv[i]+=wv[i-1];
		for(int i=1;i<=cnt;i++)od[wv[len[i]]--]=i;
		for(int i=cnt;i>=1;i--)rht[fa[od[i]]]+=rht[od[i]];
	}

	void Build_Tree(){
		int l=strlen(s+1);
		for(int i=l;i>=1;i--)Insert(s[i]-'a');
		for(int i=l;i>=1;i--)
			for(int x=id[i],p=l+1;x&&!pos[x];x=fa[x])
				p-=len[x]-len[fa[x]],pos[x]=p;
		for(int x=2;x<=cnt;x++)son[fa[x]][s[pos[x]]-'a']=x;	
	}

	void DFS(int x,int l){
		if(end[x])sa[rank[l-len[x]+1]=++tot]=l-len[x]+1;
		for(int i=0;i<26;i++)if(son[x][i])DFS(son[x][i],l);
	}

	void Build_SA(){
		int l=strlen(s+1),k=0;DFS(1,l);
		for(int i=1,j;i<=l;lcp[rank[i++]]=k)
			for(k?k--:k,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
		mm[0]=-1;
		for(int i=1;i<=l;i++){
			mm[i]=(i&(i-1))?mm[i-1]:mm[i-1]+1;
			Min[i][0]=lcp[i];
		}
		for(int k=1;k<=mm[l];k++)
			for(int i=1;i+(1<<k-1)<=l;i++)
				Min[i][k]=min(Min[i][k-1],Min[i+(1<<(k-1))][k-1]);
	}
	
	int LCP(int x,int y){
		if(x>y)swap(x,y);x+=1;int k=mm[y-x+1];
		int ret=min(Min[x][k],Min[y-(1<<k)+1][k]);
		return ret; 
	}
}A,B;

int ln,T,f[N],g[N];char s[N];
int Get_LCP(int x,int y){return A.LCP(A.rank[x],A.rank[y]);}
int Get_LCS(int x,int y){return B.LCP(B.rank[ln-x+1],B.rank[ln-y+1]);} 

int main(){
	freopen("excellent.in","r",stdin);
	freopen("excellent.out","w",stdout);
	scanf("%d",&T);
	while(T--){
		A.Init();B.Init();
		scanf("%s",s+1);ln=strlen(s+1);
		for(int i=1;i<=ln;i++){A.s[i]=s[i];B.s[i]=s[ln-i+1];}
		A.Build_Tree();A.Build_SA();
		B.Build_Tree();B.Build_SA();
		for(int i=1;i<=ln;i++)f[i]=g[i]=0;
	    
	    for(int i=1,l,r,x;i+i<=ln;i++)
			for(int j=i;(x=j+i)<=ln;j+=i)if(s[j]==s[x]){
				l=x-Get_LCS(j,x)+1;r=x+Get_LCP(j,x)-1;
				l=max(l+i-1,x);r=min(r,x+i-1);
				if(l>r)continue;
				f[l]++,f[r+1]--;
       			g[l-i-i+1]++,g[r+1-i-i+1]--;
	    	}
		long long ans=0;
		for(int i=1;i<=ln;i++)f[i]+=f[i-1],g[i]+=g[i-1];
		for(int i=1;i<ln;i++)ans+=f[i]*g[i+1];
		printf("%lld\n",ans);
	}
	return 0;
}