Luogu

LOJ

分析

设 $L_i$ 表示以 $i$ 为左端点的 AA 串的数量，$R_i$ 表示以 $i$ 为右端点的 AA 串的数量，则答案为
$$
\sum_{i=2}^nR_{i-1}\times L_i
$$
考虑计算 $L_i$ 和 $R_i$。

暴力就是 $\mathcal{O}(n^2)$ 枚举并用哈希 $\mathcal{O}(1)$ 判断，这样子可以拿 95 分。

考虑枚举 A 的长度 $l$，然后把所有是 $l$ 的倍数的位置标成关键点，则每个 AA 都会跨过两个关键点。

于是考虑计算相邻的两个关键点 $i,j$ 对答案的贡献。

设 $x=\operatorname{lcp}(suf(i),suf(j)),y=\operatorname{lcs}(pre(i-1),pre(j-1))$。可以发现，如果 $x+y<l$，则不可能构成 AA；否则会有 $x+y-l$ 个满足条件的 AA， 此时相当于要对 $L,R$ 区间加，差分即可。

需要注意的是为了避免影响到不该计算到的部分，需要将 $x$ 对 $l$ 取 $\min$、$y$ 对 $l-1$ 取 $\min$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=30000+10;

int n; char s[N];
int L[N],R[N];

struct SuffixArray {
    int sa[N],rnk[N],height[N];
    int x[N],y[N],z[N];
    int lg[N],f[15][N];
    void init() { memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); }
    void SuffixSort() {
        int m=122;
        for (int i=1;i<=m;++i) z[i]=0;
        for (int i=1;i<=n;++i) ++z[x[i]=s[i]];
        for (int i=2;i<=m;++i) z[i]+=z[i-1];
        for (int i=n;i;--i) sa[z[x[i]]--]=i;
        for (int k=1;k<=n;k<<=1) {
            int p=0;
            for (int i=n-k+1;i<=n;++i) y[++p]=i;
            for (int i=1;i<=n;++i) if (sa[i]>k) y[++p]=sa[i]-k;
            for (int i=1;i<=m;++i) z[i]=0;
            for (int i=1;i<=n;++i) ++z[x[i]];
            for (int i=2;i<=m;++i) z[i]+=z[i-1];
            for (int i=n;i;--i) sa[z[x[y[i]]]--]=y[i],y[i]=0;
            swap(x,y),x[sa[1]]=p=1;
            for (int i=2;i<=n;++i)
                x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?p:++p;
            if (p==n) break; m=p;
        }
    }
    void GetHeight() {
        for (int i=1;i<=n;++i) rnk[sa[i]]=i;
        for (int i=1,j=0;i<=n;++i) {
            if (j) --j; int p=sa[rnk[i]-1];
            for (;s[i+j]==s[p+j];++j);
            height[rnk[i]]=j;
        }
    }
    void buildST() {
        for (int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
        for (int i=1;i<=n;++i) f[0][i]=height[i];
        for (int i=1;i<15;++i)
            for (int j=1;j<=n;++j)
                f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
    }
    int qmin(int x,int y) {
        int t=lg[y-x+1];
        return min(f[t][x],f[t][y-(1<<t)+1]);
    }
    int LCP(int x,int y) {
        if (rnk[x]>rnk[y]) swap(x,y);
        return qmin(rnk[x]+1,rnk[y]);
    }
} A,B;

int main() {
    int T=read();
    while (T--) {
        scanf("%s",s+1); n=strlen(s+1);
        A.init(),A.SuffixSort(),A.GetHeight(),A.buildST();
        reverse(s+1,s+n+1);
        B.init(),B.SuffixSort(),B.GetHeight(),B.buildST();
        for (int i=1;i<=n;++i) L[i]=R[i]=0;
        for (int l=1;l<=n/2;++l)
            for (int i=l,j=l<<1;j<=n;i+=l,j+=l) {
                int x=min(A.LCP(i,j),l),y=min(B.LCP(n-i+2,n-j+2),l-1);
                if (x+y>=l) {
                    int t=x+y-l;
                    ++L[i-y],--L[i-y+t+1];
                    ++R[j+x-t-1],--R[j+x];
                }
            }
        for (int i=1;i<=n;++i) L[i]+=L[i-1],R[i]+=R[i-1];
        ll ans=0;
        for (int i=2;i<=n;++i) ans+=1ll*R[i-1]*L[i];
        printf("%lld\n",ans);
    }
    return 0;
}