B Spirit Circle Observation

感谢@RedreamMer 巨佬 找到了我题解中的致命错误

Updata by 2022/7/20 15:29

构造的数据

#include <bits/stdc++.h>
using namespace std;
int a = 1e5;
int main() {
    freopen("a.in", "w", stdout);
    string s;
    for (int i = 1; i <= a; ++i) s.push_back('0');
    s.push_back('1');
    for (int i = 1; i <= a; ++i) s.push_back('0');
    for (int i = 1; i <= a; ++i) s.push_back('9');
    std::cout << s.size() << '\n' << s << '\n';
    return 0;
}

$SAMSAM$求出$endposendpos$然后枚举最后一位不是$99$的情况

我们枚举的是上面一个节点，贡献是

接下来枚举$A+c+99\dots 9A+c+99\backslash dots9$ 与 $B+(char)(c+1)+00\dots 0B+(char)(c+1)+00\backslash dots0$配对的情况

就是$SAMSAM$上枚举每个节点下方的子节点

如枚举到节点 $ii$ 然后就枚举$o=ch[i][j],p=ch[i][j+1](0\le j\le 8)o=ch[i][j],p=ch[i][j+1](0\backslash le\; j\backslash le\; 8)$ 然后就$oo$一直走$99$的那一边,$pp$一直走$00$的一边，边走边统计，计算方式如上

这样是暴力会被卡成$O(n^2)O(n^2)$

官方题解给出了明确的说法，$p1,p2p1,p2$ 这样的关键点对只有$nn$个，$ch[p1][9],ch[p2][0]ch[p1][9],ch[p2][0]$最多也只有$nn$个，我们就用$mapmap$ 暴力存下所有点对及下方字符串的$endpos(x)\times endpos(y)endpos(x)\backslash times\; endpos(y)$ 然后计算即可

#include <bits/stdc++.h>
typedef long long LL;

const int N = 8e5 + 1000;
int ch[N][10], last = 1, siz[N], Link[N], tot = 1, len[N];
char s[N];
std::vector<int> G[N];

void insert(int c) {
    int o = ++ tot, p = last; len[o] = len[p] + 1; siz[o] = 1;
    for (; p && ch[p][c] == 0; p = Link[p]) ch[p][c] = o;
    if (!p) Link[o] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) Link[o] = q;
        else {
            int nq = ++ tot;
            Link[nq] = Link[q];
            len[nq] = len[p] + 1;
            Link[q] = Link[o] = nq;
            memcpy(ch[nq], ch[q], sizeof(ch[nq]));
            for (;ch[p][c] == q; p = Link[p]) ch[p][c] = nq;
        }
    }
    last = o;
}

void dfs(int x) {
    for (auto y : G[x]) {
        dfs(y);
        siz[x] += siz[y];
    }
}

void Get() {
    for (int i = 2; i <= tot; ++ i) G[Link[i]].push_back(i);
    dfs(1);
}

std::map<std::pair<int, int>, LL> mp;

LL Get(int x, int y) {
    if (!x || !y) return 0;
    if (mp.find({x, y}) != mp.end()) return mp[{x, y}];
    return mp[{x, y}] += (LL)Get(ch[x][9], ch[y][0]) + (LL)siz[x] * siz[y];
}

void work() {
    LL ans = 0; siz[0] = 0; len[0] = -1;
    for (int i = 1; i <= tot; ++ i) {
        for (int j = 0; j < 9; ++ j) {
            int o = ch[i][j], p = ch[i][j + 1];
            ans += (LL)(siz[o] * siz[p] + Get(ch[o][9], ch[p][0])) * (len[i] - len[Link[i]]);
        }
    }
    std::cout << ans << std::endl;
}

int main() {
    int n;
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; ++ i) insert(s[i] - 48);
    Get(); work();
    return 0;
}

原代码

#include <bits/stdc++.h>
typedef long long LL;

const int N = 8e5 + 1000;
int ch[N][10], last = 1, siz[N], Link[N], tot = 1, len[N];
char s[N];
std::vector<int> G[N];

void insert(int c) {
    int o = ++ tot, p = last; len[o] = len[p] + 1; siz[o] = 1;
    for (; p && ch[p][c] == 0; p = Link[p]) ch[p][c] = o;
    if (!p) Link[o] = 1;
    else {
        int q = ch[p][c];
        if (len[q] == len[p] + 1) Link[o] = q;
        else {
            int nq = ++ tot;
            Link[nq] = Link[q];
            len[nq] = len[p] + 1;
            Link[q] = Link[o] = nq;
            memcpy(ch[nq], ch[q], sizeof(ch[nq]));
            for (;ch[p][c] == q; p = Link[p]) ch[p][c] = nq;
        }
    }
    last = o;
}

void dfs(int x) {
    for (auto y : G[x]) {
        dfs(y);
        siz[x] += siz[y];
    }
}

void Get() {
    for (int i = 2; i <= tot; ++ i) G[Link[i]].push_back(i);
    dfs(1);
}

void work() {
    LL ans = 0; siz[0] = 0; len[0] = -1;
    for (int i = 1; i <= tot; ++ i) {
        for (int j = 0; j < 9; ++ j) {
            int o = ch[i][j], p = ch[i][j + 1];
            while (o && p) {
                ans += ((LL)siz[o] * siz[p]) * (LL)(len[i] - len[Link[i]]);
                o = ch[o][9];
                p = ch[p][0];
            }
        }
    }
    std::cout << ans << std::endl;
}

int main() {
    int n;
    scanf("%d%s", &n, s + 1);
    for (int i = 1; i <= n; ++ i) insert(s[i] - 48);
    Get(); work();
    return 0;
}