2022牛客暑假多校01B[Spirit Circle Observation]

大致题意

给出一个长度为\(n\)的字符串\(s\)，求有多少个子串对\((A,B)\)，满足

\(1. |A| = |B|\)

\(2. \overline{A} + 1 = \overline{B}\)

解题思路

前置知识点：SAM(后缀自动机)

经过思考我们可以发现，我们可以将题目所求的字符串转化为\(A = t(x)9999...,B = t(x + 1)0000...\)，\(t\)为一任意子串，\(x\)为\(0-8\)之间的数，后缀的\(0\)和\(9\)的数量相同。

得到这一性质后，我们可以考虑用SAM处理该问题。将所有的字符插入后缀自动机，自动机上的每一个节点，对应一个\(t\)的等价类，等价类的大小为\(a[i].len - a[a[i].link].len\)。

对于每一个等价类，我们可以暴力向后查询\((x)9999...\)和\((x + 1)0000...\)的节点，将对应的一对节点大小相乘，再乘上等价类的大小，即为我们所需的答案。

具体实现可以看代码

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 4e5 + 10;
int sz[maxn * 2 + 10];
namespace SAM {
    struct node
    {
        int len, link, nxt[10];
    } a[maxn << 1];
    int         las = 0, tot = 0;
    inline void init()
    {
        las = 1;
        tot = 1;
        a[1].link = 0;
    }
    inline void insert(int x)
    {
        int cur = ++tot;
        a[tot].len = a[las].len + 1;
        sz[tot] = 1;
        int p = las;
        while (p != 0 && !a[p].nxt[x]) {
            a[p].nxt[x] = cur;
            p = a[p].link;
        }
        if (p == 0)
            a[cur].link = 1;
        else {
            int q = a[p].nxt[x];
            if (a[p].len + 1 == a[q].len)
                a[cur].link = q;
            else {
                int clone = ++tot;
                a[clone] = a[q];
                a[clone].len = a[p].len + 1;
                a[q].link = a[cur].link = clone;
                while (p != 0 && a[p].nxt[x] == q) {
                    a[p].nxt[x] = clone;
                    p = a[p].link;
                }
            }
        }
        las = cur;
    }
}  // namespace SAM
using namespace SAM;

vector<int> edges[2 * maxn + 10];
void        dfs(int p)
{
    for (auto q : edges[p]) {
        dfs(q);
        sz[p] += sz[q];
    }
}
ll   ans = 0;
void dfs2(int p)
{
    ll cnt = a[p].len - a[a[p].link].len;
    for (int i = 0; i < 9; i++) {
        int x = a[p].nxt[i];
        int y = a[p].nxt[i + 1];
        while(x > 0 && y > 0) {
            ans += sz[x] * sz[y] * cnt;
            x = a[x].nxt[9];
            y = a[y].nxt[0];
        }
    }
    for (auto q : edges[p])
        dfs2(q);
}
string s;
int    n;

void solve()
{
    cin >> n;
    cin >> s;
    init();
    for (int i = 0; i < n; i++) {
        insert(s[i] - '0');
    }
    for (int i = 2; i <= tot; i++) {
        edges[a[i].link].emplace_back(i);
    }
    dfs(1);
    a[0].len = -1;
    dfs2(1);
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

参考博客：(11条消息) 2022”蔚来杯“牛客多校第一场 B. Spirit Circle Observation【SAM】_胡步的博客-CSDN博客