记录编号	486098	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]优秀的拆分	最终得分	100
用户昵称	支羽	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2018-02-05 11:43:18	内存使用	1.48 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#define LL unsigned long long
#define FILE "excellent"
//#define FILE "优秀的拆分"
#define pow _pow
using namespace std;

const int N = 100010;
const LL Base = 19491001;
LL pow[N],hsh[N],Ans;
int n,pre[N],suf[N];
char s[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9' || ch<'0')res^=ch=='-',ch=getchar();
  while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
  return res?x:-x;
}

inline void hash_string(){
  pow[0]=1;hsh[0]=0;
  for(int i=1;i<=n;++i){
    pow[i]=pow[i-1]*Base;
    hsh[i]=hsh[i-1]*Base+(s[i]-'a'+1);
  }
}

inline LL geth(int l,int r){
  return hsh[r]-hsh[l-1]*pow[r-l+1];
}

inline void solve(){
  scanf("%s",s+1);n=strlen(s+1);
  hash_string();
  for(int L=1;L*2<n;++L){
    for(int i=L+L;i<=n;i+=L){
      if(s[i]!=s[i-L])continue;
      int hd,tl,lst=i-L;
      int l,r,ans;
      
      // (<- |    <- |)
      l=1;r=L;ans=0;
      while(l<=r){
        int mid=(l+r)>>1;
        if(geth(lst-mid+1,lst)==geth(i-mid+1,i))
          ans=mid,l=mid+1;
        else r=mid-1;
      }
      hd=i-ans+1;

      // (| ->    | ->)
      l=1;r=L;ans=0;
      while(l<=r){
        int mid=(l+r)>>1;
        if(geth(lst,lst+mid-1)==geth(i,i+mid-1))
          ans=mid,l=mid+1;
        else r=mid-1;
      }
      tl=i+ans-1;

      hd=hd+L-1;if(hd>tl)continue;
      pre[hd]++;pre[tl+1]--;
      suf[hd-L-L+1]++;suf[tl-L-L+2]--;
    }
  }
  Ans=0;
  for(int i=1;i<=n;++i)
    pre[i]+=pre[i-1],suf[i]+=suf[i-1];
  for(int i=1;i<n;++i)
    Ans+=1ll*pre[i]*suf[i+1];
  printf("%llu\n",Ans);
  for(int i=0;i<=n+n+1;++i)
    pre[i]=suf[i]=0,pow[i]=hsh[i]=0;
}

int main(){
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  int Case=gi();while(Case--)solve();
  fclose(stdin);fclose(stdout);
  return 0;
}