QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#599353 | #7876. Cyclic Substrings | Hirro | AC ✓ | 1425ms | 1037592kb | C++20 | 5.3kb | 2024-09-29 03:41:14 | 2024-09-29 03:41:14 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#define pll pair<int,int>
#define dep(x) tr[x].dep
using namespace std;
const int N = 3e6 + 5;
const int LOG = 23;
int tot = 2, root[2] = { 2,1 };
struct node {
int val, dep,son[10],tg ;
}tr[N * 2];
int fa[N * 2][LOG+1], pos[N * 4], r[N * 4], lg[N * 2 + 1], ci[31];
int t[N * 4], tn = 0, n;
const int P = 998244353;
string s;
int insert(int f, int ty, int val) {
int& x = tr[f].son[ty];
if (x == 0) {
x = ++tot;
fa[x][0] = f;
for (int i = 1; i <= LOG; i++)fa[x][i] = fa[fa[x][i - 1]][i - 1];
dep(x) = dep(f) + 2;
}
tr[x].val += val;
return x;
}
int ans = 0;
int up(int x, int dis) {
dis = max(dis, 0);
for (int j = lg[dis]; j >= 0; j = lg[dis]) {
dis -= ci[j];
x = fa[x][j];
}
return x;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("1.in", "r", stdin);
cin >> n >> s;
t[tn++] = 10;
for (auto& v : s) {
t[tn++] = v - '0';
t[tn++] = 10;
}
for (auto& v : s) {
t[tn++] = v - '0';
t[tn++] = 10;
}
fa[1][0] = 1, fa[2][0] = 2;
dep(1) = -1;
for (int i = 1; i <= N * 2; i++)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
for (int i = 0; i <= N * 2; i++)lg[i]--;
for (int i = 1; i <= LOG; i++)fa[1][i] = fa[fa[1][i - 1]][i - 1];
for (int i = 1; i <= LOG; i++)fa[2][i] = fa[fa[1][i - 1]][i - 1];
for (int i = 0; i <= 30; i++)ci[i] = 1 << i;
int mid = 0;
for (int i = 0; i <= 2 * n; i++) {
int rt = root[i % 2];
if (mid + r[mid] > i) {
int nx = 2 * mid - i;
r[i] = min(mid + r[mid] - i, r[nx]);
int L = i + r[i], R = i + r[nx];
L += L % 2, R += R % 2;
pos[i] = up(pos[nx], (R - L) / 2);
tr[rt].tg--;
tr[pos[i]].tg++;
}
if (!pos[i])pos[i] = t[i] == 10 ? pos[i] = rt : insert(rt, t[i], 1);
while (i + r[i] + 1 < tn && i - r[i] - 1 >= 0 && t[i + r[i] + 1] == t[i - r[i] - 1]) {
r[i]++;
if (t[i + r[i]] != 10)pos[i] = insert(pos[i], t[i + r[i]], 1);
}
if (i + r[i] > mid + r[mid])mid = i;
}
for (int i = 2 * n + 1; i < tn; i++) {
int rt = root[i % 2];
int nx = 2 * mid - i;
r[i] = max(r[i - 2 * n], min(mid + r[mid] - i, r[nx]));
if (min(mid + r[mid] - i, r[nx]) < r[i - 2 * n])nx = i - 2 * n;
int L = i - r[nx], R = i - r[i];
L -= L % 2, R -= R % 2;
pos[i] = up(pos[nx], (R - L) / 2);
if (i - r[i] < 2 * n) {
L = i - r[nx], R = 2 * n;
L -= L % 2, R -= R % 2;
int x = up(pos[nx], (R - L) / 2);
tr[x].tg--;
tr[pos[i]].tg++;
}
while (i + r[i] + 1 < tn && i - r[i] - 1 >= 0 && t[i + r[i] + 1] == t[i - r[i] - 1]) {
r[i]++;
if (t[i + r[i]] != 10)pos[i] = insert(pos[i], t[i + r[i]], i - r[i] < 2 * n);
}
if (i + r[i] > mid + r[mid])mid = i;
}
for (int u = tot; u >= 1; u--) {
int f = fa[u][0];
tr[f].tg = (tr[f].tg + tr[u].tg) % P;
tr[u].val = (tr[u].val + tr[u].tg) % P;
if (dep(u) <= n)ans = (ans + 1ll * tr[u].val * tr[u].val % P * dep(u) % P) % P;
}
cout << (ans % P + P) % P << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 15ms
memory: 33000kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 11ms
memory: 31276kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 4ms
memory: 31308kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 11ms
memory: 33064kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 11ms
memory: 31364kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 3ms
memory: 32828kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 11ms
memory: 32436kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 341ms
memory: 369024kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: 0
Accepted
time: 1232ms
memory: 1037560kb
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
output:
890701718
result:
ok 1 number(s): "890701718"
Test #10:
score: 0
Accepted
time: 418ms
memory: 564244kb
input:
3000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
224009870
result:
ok 1 number(s): "224009870"
Test #11:
score: 0
Accepted
time: 1425ms
memory: 1037592kb
input:
3000000 8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...
output:
51985943
result:
ok 1 number(s): "51985943"
Test #12:
score: 0
Accepted
time: 1261ms
memory: 1037568kb
input:
3000000 1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...
output:
355676465
result:
ok 1 number(s): "355676465"
Test #13:
score: 0
Accepted
time: 839ms
memory: 933428kb
input:
3000000 7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...
output:
788510374
result:
ok 1 number(s): "788510374"
Test #14:
score: 0
Accepted
time: 819ms
memory: 965564kb
input:
3000000 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555...
output:
691884476
result:
ok 1 number(s): "691884476"
Test #15:
score: 0
Accepted
time: 392ms
memory: 604676kb
input:
3000000 0990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990...
output:
701050848
result:
ok 1 number(s): "701050848"
Test #16:
score: 0
Accepted
time: 205ms
memory: 302048kb
input:
3000000 2772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772...
output:
486861605
result:
ok 1 number(s): "486861605"
Test #17:
score: 0
Accepted
time: 704ms
memory: 908048kb
input:
3000000 4554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554...
output:
450625621
result:
ok 1 number(s): "450625621"
Test #18:
score: 0
Accepted
time: 699ms
memory: 885032kb
input:
3000000 1181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181...
output:
649551870
result:
ok 1 number(s): "649551870"
Extra Test:
score: 0
Extra Test Passed