QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#599353#7876. Cyclic SubstringsHirroAC ✓1425ms1037592kbC++205.3kb2024-09-29 03:41:142024-09-29 03:41:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-29 03:41:14]
  • 评测
  • 测评结果:AC
  • 用时:1425ms
  • 内存:1037592kb
  • [2024-09-29 03:41:14]
  • 提交

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