记录编号	357015	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]优秀的拆分	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.458 s
提交时间	2016-12-08 13:03:43	内存使用	1.95 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
 
typedef unsigned long long int ULL;
 
const int prime[]={59,3,41,43,47,71,5,7,11,13,61,19,23,29,31,37,73,53,2,17,67,79,83,89,97,101};
 
int read(char *s){
	char *p=s,ch;
	while(ch=getchar(),!isalpha(ch)) if(ch==EOF) return 0;
	while((*(++p))=ch,ch=getchar(),isalpha(ch));
	return p-s;
}
#define HASH(i,l) (hash[i]-hash[i+l]*xpow[l])
#define HASH2(i,l) (hash2[i+l-1]-hash2[i-1]*xpow[l])
 
struct suf{
	ULL hash[30010],x,xpow[30010],hash2[30010];
	int n; char str[30010];
	void init(ULL _x){
		xpow[0]=1; x=_x;
		for(int i=1;i<=30000;xpow[i]=xpow[i-1]*x,i++);
	}
	void reset(){
		n=strlen(str+1); hash[n+1]=0; 
		for(int i=n;i>=1;i--) hash[i]=hash[i+1]*x+prime[str[i]-'a'];
		//for(int i=1;i<=n;i++) hash2[i]=hash2[i-1]*x+prime[str[i]-'a'];
	}
	int erfen(int x,int y,int limit){
		int l=0,r=limit,ans=0,mid;
		while(l<=r){
			mid=(l+r)>>1;
			if(HASH(x,mid)==HASH(y,mid)/*&&HASH2(x,mid)==HASH2(y,mid)*/) ans=mid,l=mid+1;
			else r=mid-1;
		}
		return ans;
	}
}s1,s2;
 
long long ans;
int len,f[30010],g[30010];
 
int main()
{
	//freopen("a.txt","r",stdin);
	freopen("excellent.in","r",stdin);
	freopen("excellent.out","w",stdout);
	s1.init(29); s2.init(4157);
	while(len=read(s1.str),len){
		s1.str[len+1]=s2.str[len+1]='\0';
		for(int i=1;i<=len;i++) s2.str[len-i+1]=s1.str[i];
		memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
		s1.reset(); s2.reset();
		for(int i=1;i<=len;i++)
			for(int l=i;l+i<=len;l+=i){
				int q=s2.erfen(len-l-i+1,len-l+1,i),p=s1.erfen(l,l+i,i);
				if(i-p-q<0){
					f[l-q+1]++;f[l+p-i+1]--;
					g[l+i+i-q]++;g[l+i+p]--;
				}
			}
		ans=0;
		for(int i=1;i<=len;i++) f[i]+=f[i-1],g[i]+=g[i-1],ans+=f[i]*g[i-1];
		printf("%lld\n",ans);
	}
	return 0;
}