记录编号	347344	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]优秀的拆分	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2016-11-13 09:45:48	内存使用	21.85 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
typedef long long ll;
int T,n,sa[N],r[N],h[N],Wa[N],Wb[N],Ws[N],Wv[N];
char s[N];
bool cmp(int *r,int x,int y,int l){
	return r[x]==r[y]&&r[x+l]==r[y+l];
}
void da(){
	int i,*x=Wa,*y=Wb,m=500,p=0,l=1;
	for (i=0;i<=m;i++) Ws[i]=0;
	for (i=1;i<=n;i++) Ws[x[i]=s[i]]++;
	for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
	for (i=n;i;i--) sa[Ws[x[i]]--]=i;
	for (;p<n;m=p,l<<=1){
		for (i=n-l+1,p=0;i<=n;i++) y[++p]=i;
		for (i=1;i<=n;i++)
			if (sa[i]>l) y[++p]=sa[i]-l;
		for (i=1;i<=n;i++) Wv[i]=x[y[i]];
		for (i=0;i<=m;i++) Ws[i]=0;
		for (i=1;i<=n;i++) Ws[Wv[i]]++;
		for (i=1;i<=m;i++) Ws[i]+=Ws[i-1];
		for (i=n;i;i--) sa[Ws[Wv[i]]--]=y[i];
		swap(x,y);
		for (p=x[sa[1]]=1,i=2;i<=n;i++)
			x[sa[i]]=cmp(y,sa[i],sa[i-1],l)?p:++p;
	}
}
int dp[N][18],lg[N],t[18];
void geth(){
	int i,j,k;
	for (i=1;i<=n;i++) r[sa[i]]=i;
	for (k=h[r[0]]=0,i=1;i<=n;h[r[i++]]=k)
	for (k=max(h[r[i-1]]-1,0),j=sa[r[i]-1];s[i+k]==s[j+k];k++);
	for (i=1;i<=n;i++) dp[i][0]=h[i];
	for (j=1;j<18;j++)
	for (i=1;i<=n-t[j]+1;i++)
		dp[i][j]=min(dp[i][j-1],dp[i+t[j-1]][j-1]);
}
int lcp(int x,int y){
	x=r[x];y=r[y];
	if (x>y) swap(x,y);
	int k=lg[y-x];
	return min(dp[x+1][k],dp[y-t[k]+1][k]); 
}
int pos(int x){return n*2+2-x;}
int Start[N],End[N];
int main()
{
	freopen("excellent.in","r",stdin);
	freopen("excellent.out","w",stdout);
	t[0]=1;
	for (int i=1;i<18;i++){
		t[i]=1<<i;
		for (int j=t[i-1];j<t[i];j++) lg[j]=i-1;
	}
	scanf("%d",&T);
	while (T--){
		memset(Wa,0,sizeof Wa);
		memset(Wb,0,sizeof Wb);
		memset(s,0,sizeof s);
		memset(sa,0,sizeof sa);
		memset(r,0,sizeof r);
		memset(h,0,sizeof h);
		memset(Start,0,sizeof Start);
		memset(End,0,sizeof End);
		scanf("%s",s+1);
		n=strlen(s+1);
		for (int i=1;i<=n;i++) s[pos(i)]=s[i];
		s[0]='#';s[n*2+2]='*';
		n=n*2+1;da();geth();n/=2;
		for (int L=1;L<=n;L++){//枚举AA中A的长度，或BB中B的长度 
			for (int i=L+L;i<=n;i+=L){
				int suc=lcp(i-L,i),pre=lcp(pos(i-L),pos(i));
				int len=pre+suc-L,l=i-L-pre+1,r=i+suc-1;
				if (len>0){
					Start[l]++;Start[l+len]--;
					End[r-len+1]++;End[r+1]--;
					i=r+1-L;
				}
			}
		}
		for (int i=1;i<=n;i++) Start[i]+=Start[i-1];
		for (int i=1;i<=n;i++) End[i]+=End[i-1];
		ll ans=0;
		for (int i=1;i<n;i++) ans+=(ll)End[i]*Start[i+1];
		printf("%lld\n",ans);
	}
	return 0;
}