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$的情况

$\sum _{i=1}^{tot}\sum _{j=0}^{8}endpos\left(ch\left[i\right]\left[j\right]\right)×endpos\left(ch\left[i\right]\left[j+1\right]\right)×\left(len\left[i\right]-len\left[Link\left[i\right]\right)\sum_\left\{i=1\right\}^\left\{tot\right\}\sum_\left\{j=0\right\}^\left\{8\right\}endpos\left(ch\left[i\right]\left[j\right]\right)\times endpos\left(ch\left[i\right]\left[j+1\right]\right)\times \left(len\left[i\right]-len\left[Link\left[i\right]\right)$

#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;
else {
int q = ch[p][c];
if (len[q] == len[p] + 1) Link[o] = q;
else {
int nq = ++ tot;
len[nq] = len[p] + 1;
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;
else {
int q = ch[p][c];
if (len[q] == len[p] + 1) Link[o] = q;
else {
int nq = ++ tot;
len[nq] = len[p] + 1;
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;
}