[NOI 2016]优秀的拆分

Description

题库链接

给你一个长度为 \(n\) 的只含小写字母的字符串 \(S\) ，计算其子串有多少优秀的拆分。

如果一个字符串能被表示成 \(AABB\) 的形式，其中 \(A,B\) 非空，那么称 \(AABB\) 是一个优秀的拆分。一个子串可能有多个优秀的拆分。

多组询问，询问组数 \(T\) 。

\(1\leq n\leq 30000,1\leq T\leq 10\)

Solution

会用这题的方法的话，应该不难想。

如果记 \(s_{1_i}\) 为以 \(i\) 结尾的 \(AA\) 串个数，记 \(s_{2_i}\) 为以 \(i\) 开头的 \(BB\) 串个数。

那么答案就是 \(\sum\limits_{i=2}^n s_{1_{i-1}}\times s_{2_i}\)

考虑如何求 \(s_1\) 或 \(s_2\) 。

我们可以枚举 \(A\) 的长度 \(l\) ，用 \(i,i+l\) 这两个点可以将所有的长度为 \(2l\) 的 \(AA\) 并且同一个长度为 \(2l\) 的 \(AA\) 不会被不同的一组 \(i,i+l\) 固定。

这样对于每一组 \(i,i+l\) ，我们设法去计算它所固定的长度为 \(2l\) 的 \(AA\) 。

可以求出 \(i,i+l\) 的最长公共前缀 \(x\) ， \(i,i+l\) 的最长公共后缀 \(y\) ，如果 \(x+y\geq l\) ，那么存在长度为 \(2l\) 的 \(AA\) 经过 \(i,i+l\) 。

求出区间左端点 \(L=\max\{i-x+1, i-l+1\}\) ，右端点 \(R=\min\{i-l+y+1, i\}\) 。

显然这一段区间都是能够对答案产生贡献的，差分一下即可。

下发的几个样例字符串长度都是递增的...大样例过了自信 AC ，结果因为没清空数组 wa 成苟

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 30000+5;

int bin[35], lgn[N], t, n, m, x[N<<1], y[N<<1], c[N];
ll s1[N], s2[N];

struct SA {
    char ch[N];
    int sa[N], rk[N], height[N], f[30][N];
    void get() {
        for (int i = 1; i <= n*2; i++) x[i] = y[i] = 0;
        for (int i = 1; i <= m; i++) c[i] = 0;
        for (int i = 1; i <= n; i++) c[x[i] = ch[i]]++; 
        for (int i = 2; i <= m; i++) c[i] += c[i-1];
        for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int 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;
            for (int i = 1; i <= m; i++) c[i] = 0;
            for (int i = 1; i <= n; i++) c[x[i]]++;
            for (int i = 2; i <= m; i++) c[i] += c[i-1];
            for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
            swap(x, y); x[sa[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 ((m = num) == n) break;
        }
        for (int i = 1; i <= n; i++) rk[sa[i]] = i;
        for (int i = 1, k = 0; i <= n; i++) {
            if (rk[i] == 1) continue;
            if (k) --k; int j = sa[rk[i]-1];
            while (i+k <= n && j+k <= n && ch[i+k] == ch[j+k]) ++k;
            height[rk[i]] = k;
        }
    }
    void rmq() {
        int t = lgn[n];
        for (int i = 1; i <= n; i++) f[0][i] = height[i];
        for (int i = 1; i <= t; i++)
            for (int j = 1; j+bin[i-1] <= n; j++)
                f[i][j] = min(f[i-1][j], f[i-1][j+bin[i-1]]);
    }
    int lcp(int a, int b) {
        a = a > n ? 0 : rk[a], b = b > n ? 0 : rk[b];
        if (a > b) swap(a, b); ++a;
        int t = lgn[b-a+1];
        return min(f[t][a], f[t][b-bin[t]+1]);
    }
}b, f;
void work() {
    bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = (bin[i-1]<<1);
    lgn[0] = -1; for (int i = 1; i < N; i++) lgn[i] = lgn[i>>1]+1;
    scanf("%d", &t);
    while (t--) {
        memset(s1, 0, sizeof(s1)), memset(s2 ,0, sizeof(s2));
        scanf("%s", f.ch+1); n = strlen(f.ch+1);
        for (int i = 1; i <= n; i++) b.ch[n-i+1] = f.ch[i];
        m = 255; f.get(); f.rmq(); m = 255; b.get(); b.rmq();
        for (int l = 1; l <= n; l++)
            for (int i = 1; i+l <= n; i += l) {
                int x = b.lcp(n-i+1, n-(i+l)+1), y = f.lcp(i+1, i+l+1);
                if (x+y < l) continue;
                int L = max(i-x+1, i-l+1), R = min(i-l+y+1, i);
                if (L > R) continue;
                s1[L+l*2-1]++, s1[R+l*2]--;
                s2[L]++, s2[R+1]--;
            }
        for (int i = 2; i <= n; i++) s1[i] += s1[i-1], s2[i] += s2[i-1];
        ll ans = 0;
        for (int i = 2; i <= n; i++) ans += 1ll*s1[i-1]*s2[i];
        printf("%lld\n", ans);
    }
}
int main() {work(); return 0; }