记录编号	408555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2016]优秀的拆分	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.310 s
提交时间	2017-05-24 21:52:14	内存使用	33.28 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 30000
#define LOG4N 17
using namespace std;
 
#ifdef _WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
 
int n,l2[4*MAXN+10],f[MAXN+10],g[MAXN+10];
char s[MAXN+10];
 
struct SuffixTree {
    int ch[2*MAXN+10][26],f[2*MAXN+10],a[2*MAXN+10],b[MAXN+10],n,m,last,u[2*MAXN+10],v[2*MAXN+10],p[2*MAXN+10],me,idx,e[4*MAXN+10],pos[2*MAXN+10],mi[LOG4N+1][4*MAXN+10];
    SuffixTree() {memset(ch,-1,sizeof(ch));}
    void clear() {
        memset(ch,-1,sizeof(ch[0])*(m+1));
        m=last=n=0; f[0]=-1;
    }
    void addChar(int k) {
        int p=last,np=++m; a[np]=a[p]+1; last=np; b[++n]=np;
        while (p!=-1&&ch[p][k]==-1) {ch[p][k]=np; p=f[p];}
        if (p==-1) f[np]=0;
        else {
            int q=ch[p][k];
            if (a[q]==a[p]+1) f[np]=q;
            else {
                int nq=++m; a[nq]=a[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[nq]));
                f[nq]=f[q]; f[q]=nq; f[np]=nq;
                while (p!=-1&&ch[p][k]==q) {ch[p][k]=nq; p=f[p];}
            }
        }
    }
    void addEdge(int x,int y) {
        ++me; v[me]=y; p[me]=u[x]; u[x]=me;
    }
    void dfs(int x) {
        e[++idx]=x; pos[x]=idx;
        for (int i=u[x];i;i=p[i]) {
            dfs(v[i]); e[++idx]=x;
        }
    }
    void buildTree() {
        memset(u,0,sizeof(int)*(m+1)); me=0;
        for (int i=1;i<=m;++i) addEdge(f[i],i);
        idx=0; dfs(0);
        for (int i=1;i<=idx;++i) mi[0][i]=a[e[i]];
        for (int j=0;j<LOG4N;++j)
            for (int i=1;i<=idx;++i)
                mi[j+1][i]=min(mi[j][i],mi[j][i+(1<<j)]);
        l2[0]=0; for (int i=1;i<=idx;++i) l2[i]=l2[i-1]+(i>>l2[i-1]>>1);
    }
    int lcp(int x,int y) {
        x=pos[b[x]]; y=pos[b[y]];
        if (x>y) swap(x,y); int d=l2[y-x];
        return min(mi[d][x],mi[d][y-(1<<d)+1]);
    }
}T1,T2;
 
int main() {
    freopen("excellent.in","r",stdin);
    freopen("excellent.out","w",stdout);
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%s",s+1); n=strlen(s+1);
        T1.clear(); for (int i=1;i<=n;++i) T1.addChar(s[i]-'a');
        T1.buildTree();
        T2.clear(); for (int i=n;i;--i) T2.addChar(s[i]-'a');
        T2.buildTree();
        memset(f,0,sizeof(int)*(n+2));
        memset(g,0,sizeof(int)*(n+2));
        for (int d=1;d+d<=n;++d)
            for (int i=d;i+d<=n;i+=d) {
                int x=min(d,T1.lcp(i,i+d)),y=min(d-1,T2.lcp(n-i,n-i-d));
                if (x+y>=d) {
                    ++f[i+d-x+d]; --f[i+d+y+1];
                    ++g[i+1+y-d]; --g[i-x];
                }
            }
        for (int i=1;i<=n;++i) f[i]+=f[i-1];
        for (int i=n;i;--i) g[i]+=g[i+1];
        long long ans=0;
        for (int i=1;i<=n;++i) ans+=1ll*f[i]*g[i+1];
        printf(lld "\n",ans);
    }
    fclose(stdin); fclose(stdout);
    return 0;
}