恶心的公式细节题...

Problem

问母串 $S$ 能拆分出多少个 $AABB$ 串，拆分方式不同也算不同。

Solution

考虑搞出所有的 $AA$ 串作为开头和结尾出现位置 / 次数，乘起来求和就行了。

问题是怎么求这两个数组。

考虑设置间隔为 $L$ 的关键点，则一定有 $2L$ 长的 $AA$ 串经过两个关键点。

考察相邻的两个关键点 $X,X+L$，若 $LCP(X,X+L)+LCS(X-1,X+L-1)\geq L$，则一定存在 $2L$ 长的 $AA$ 串经过两个关键点。

为了不重复统计情况，$LCP$ 与 $L$ 取最小值，$LCS$ 与 $L-1$ 取最小值（全覆盖情况仅统计一次）。

考虑 $LCP$ 与 $LCS$ 重合的部分，长度为 $2L$ 的 $AA$ 串的对称线可以是这部分中的任何一条。

令 $t=LCP+LCS-L+1$。

因此起点的左区间为 $X-LCS$，右区间为 $X-LCS+t$。

终点就是起点区间右移 $2L$ 位。

$LCP$ 和 $LCS$ 用 SA 搞出来。

也可以改成 hash+ 二分，那样是 $O(n\log^2 n)$ 的复杂度。

否则就是调和级数 $O(n\log n)$ 的复杂度。

Code

// Code by ajcxsu
// Problem: you xiu de chai fen

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

const int N=3e4+10;

int n;
char s[N];
int lo[N];
struct SA {
    static const int OP=18;
    int x[N], y[N], c[N], sa[N], hei[N][OP], m;
    bool r;
    void gsa(bool rev=0) {
        CLR(x), CLR(y), CLR(sa), CLR(hei);
        if(rev) reverse(s+1, s+1+n), r=1;
        m=500, fill(c, c+m+1, 0);
        for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
        int num;
        for(int k=1;k<=n;k<<=1) {
            num=0;
            for(int i=n-k+1;i<=n;i++) y[++num]=i;
            for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
            fill(c, c+m+1, 0);
            for(int i=1;i<=n;i++) c[x[i]]++;
            for(int i=1;i<=m;i++) c[i]+=c[i-1];
            for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
            swap(x, y), x[sa[1]]=1, num=1;
            for(int i=2;i<=n;i++)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
            if(num==n) break;
            m=num;
        }
        int k=0, j;
        for(int i=1;i<=n;i++) if(x[i]>1) {
            if(k) k--;
            j=sa[x[i]-1];
            while(s[j+k]==s[i+k]) k++;
            hei[x[i]][0]=k;
        }
        for(int j=1;j<OP;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            hei[i][j]=min(hei[i][j-1], hei[i+(1<<j-1)][j-1]);
    }
    int lcp(int a, int b) {
        if(r) a=n-a+1, b=n-b+1;
        a=x[a], b=x[b];
        if(a>b) swap(a, b); a++;
        int len=lo[b-a+1];
        return min(hei[a][len], hei[b-(1<<len)+1][len]);
    }
} A, B;

int u[N], d[N];
long long ans;
int main() {
    for(int i=1;(1<<i)<N;i++) lo[1<<i]++;
    for(int i=1;i<N;i++) lo[i]+=lo[i-1];
    int T, t;
    scanf("%d", &T);
    while(T--) {
        scanf("%s", s+1), n=strlen(s+1), A.gsa(), B.gsa(true), ans=0;
        memset(u, 0, sizeof(u)), memset(d, 0, sizeof(d));
        for(int i=1;(i<<1)<=n;i++)
            for(int j=i+i; j<=n; j+=i) {
                int lcp=A.lcp(j-i, j), lcs=B.lcp(j-i-1, j-1);
                lcp=min(lcp, i), lcs=min(lcs, i-1);
                t=lcp+lcs-i+1;
                if(t>=1) {
                    u[j-i-lcs]++, u[j-i-lcs+t]--;
                    d[j+lcp-t+1]++, d[j+lcp+1]--;
                }
            }
        int ca=0, cb=0;
        for(int i=1;i<=n;i++) {
            ca+=u[i], cb+=d[i];
            ans+=1ll*ca*cb;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-1117.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆