QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#642615#7876. Cyclic Substringsucup-team1001AC ✓372ms555152kbC++202.5kb2024-10-15 15:18:572024-10-15 15:18:57

Judging History

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

  • [2024-10-15 15:18:57]
  • 评测
  • 测评结果:AC
  • 用时:372ms
  • 内存:555152kb
  • [2024-10-15 15:18:57]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
i64 mod = 998244353;

// 回文自动机
// T 字符集大小 , base 字符集基数
template<size_t T = 26, size_t base = 'a'>
class PAM {
private:
    class Node {
    public:
        int next[T];
        int fail;
        int len;
        i64 cnt;

        int x;


        Node() {
            memset(next, 0, sizeof(next));
            fail = 0;
            len = 0;
            cnt = 0;
        }
    };

    string s;
    vector<Node> tree;
    int last;
    int lim;

    // 获取节点 , 节点指针指向 x , 字符串长度指针指向i
    int getFail(int x, int i) {
//        cerr << i - tree[x].len + 1 << " " << i << " " << i - tree[x].len - 1 << endl;
        while (i - tree[x].len + 1 >= 2 && s[i] != s[i - tree[x].len - 1]) {
            x = tree[x].fail;
        }
        return x;
    }

    int newNode(int len, int p) {
//        cerr << len << " " << p << endl;
        tree.push_back(Node());
        tree.back().len = len;
        tree.back().x = p;
        return tree.size() - 1;
    }

    void init() {
        tree.clear();
        newNode(0, -1);
        newNode(-1, -1);
        tree[0].fail = 1;
        last = 1;
    }

    void insert(int x, int i) {
        int p = getFail(last, i);
//        cerr << x << " " << i << endl;
        if (!tree[p].next[x]) {
            int np = newNode(tree[p].len + 2, x);
            tree[np].fail = tree[getFail(tree[p].fail, i)].next[x];
            tree[p].next[x] = np;
        }
        last = tree[p].next[x];
        if (i > lim) {
//            cerr << i << endl;
            tree[last].cnt++;
        }
    }

public:

    PAM(string _s, int lim) : s(_s), lim(lim) {
        init();
        s = "#" + s;
        for (int i = 1; i < s.size(); i++) {
            insert(s[i] - base, i);
        }
    }

    i64 solve() {
        i64 ans = 0;
        for (int i = tree.size() - 1; i >= 2; i--) {
            // 出现的次数
            tree[tree[i].fail].cnt += tree[i].cnt;
            tree[tree[i].fail].cnt %= mod;

            if (tree[i].len <= lim)
                ans = (ans + (tree[i].cnt * tree[i].len % mod * tree[i].cnt % mod)) % mod;
//            cerr << tree[i].len << " " << tree[i].cnt << " " << ans << endl;

        }
        return ans;
    }
};


int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = s + s;
    PAM<10, '0'> pam(s, n);
    cout << pam.solve() << endl;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3500kb

input:

5
01010

output:

39

result:

ok 1 number(s): "39"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

8
66776677

output:

192

result:

ok 1 number(s): "192"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

2
22

output:

12

result:

ok 1 number(s): "12"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

2
21

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3536kb

input:

3
233

output:

10

result:

ok 1 number(s): "10"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

3
666

output:

54

result:

ok 1 number(s): "54"

Test #8:

score: 0
Accepted
time: 64ms
memory: 142856kb

input:

1000000
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

output:

496166704

result:

ok 1 number(s): "496166704"

Test #9:

score: 0
Accepted
time: 243ms
memory: 553968kb

input:

3000000
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

output:

890701718

result:

ok 1 number(s): "890701718"

Test #10:

score: 0
Accepted
time: 226ms
memory: 292016kb

input:

3000000
9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...

output:

224009870

result:

ok 1 number(s): "224009870"

Test #11:

score: 0
Accepted
time: 216ms
memory: 554352kb

input:

3000000
8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...

output:

51985943

result:

ok 1 number(s): "51985943"

Test #12:

score: 0
Accepted
time: 236ms
memory: 554940kb

input:

3000000
1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...

output:

355676465

result:

ok 1 number(s): "355676465"

Test #13:

score: 0
Accepted
time: 301ms
memory: 553200kb

input:

3000000
7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...

output:

788510374

result:

ok 1 number(s): "788510374"

Test #14:

score: 0
Accepted
time: 372ms
memory: 555152kb

input:

3000000
5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555...

output:

691884476

result:

ok 1 number(s): "691884476"

Test #15:

score: 0
Accepted
time: 178ms
memory: 291308kb

input:

3000000
0990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990...

output:

701050848

result:

ok 1 number(s): "701050848"

Test #16:

score: 0
Accepted
time: 99ms
memory: 94764kb

input:

3000000
2772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772...

output:

486861605

result:

ok 1 number(s): "486861605"

Test #17:

score: 0
Accepted
time: 166ms
memory: 555012kb

input:

3000000
4554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554...

output:

450625621

result:

ok 1 number(s): "450625621"

Test #18:

score: 0
Accepted
time: 222ms
memory: 553768kb

input:

3000000
1181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181...

output:

649551870

result:

ok 1 number(s): "649551870"

Extra Test:

score: 0
Extra Test Passed