QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#274700#7876. Cyclic Substringsucup-team2307#ML 360ms647476kbC++201.7kb2023-12-03 20:19:492023-12-03 20:19:49

Judging History

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

  • [2023-12-03 20:19:49]
  • 评测
  • 测评结果:ML
  • 用时:360ms
  • 内存:647476kb
  • [2023-12-03 20:19:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
using vi = vector<int>;
#define sz(x) int(x.size())
#define rep(i, a, b) for(int i = (a); i < (b); i++)
struct Node {
    int jump, len;
    unordered_map<int, int> to;
};
vector<Node> tree;
void build(string s) {
    auto get_link = [&](int cur, int pos) {
        while(pos - 1 - tree[cur].len < 0 || s[pos - 1 - tree[cur].len] != s[pos])
            cur = tree[cur].jump;
        return cur;
    };

    vector<vector<int>> g(sz(s) + 2);
    vector<int> sub(sz(s) + 2);
    tree.resize(sz(s) + 2);
    tree[0].len = -1;
    tree[1].jump = 0;
    g[0].push_back(1);
    int cur = 0, sz = 2;
    rep(i, 0, sz(s)) {
        int par = get_link(cur, i);
        if(tree[par].to[s[i] - '0'] == 0) {
            tree[sz].len = tree[par].len + 2;
            tree[sz].jump = max(1, tree[get_link(tree[par].jump, i)].to[s[i] - '0']);
            g[tree[sz].jump].push_back(sz);
            tree[par].to[s[i] - '0'] = sz++;
        }
        cur = tree[par].to[s[i] - '0'];
        if(i >= s.size() / 2)
            sub[cur]++;
        // cout << i << " " << cur << " " << par << endl;
    }

    int ans = 0;
    auto dfs = [&](auto self, int v) -> void {
        for(auto i : g[v]) {
            self(self, i);
            sub[v] += sub[i];
        }
        if(tree[v].len > 0 && tree[v].len <= s.size() / 2) {
            // cout << v << " (" << tree[v].len << " " << sub[v] << endl;
            ans = (ans + tree[v].len * 1ll * (sub[v] * 1ll * sub[v] % mod)) % mod;
        }
    };
    dfs(dfs, 0);
    cout << ans << endl;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string s;
    cin >> n >> s;
    build(s + s);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
01010

output:

39

result:

ok 1 number(s): "39"

Test #2:

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

input:

8
66776677

output:

192

result:

ok 1 number(s): "192"

Test #3:

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

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #4:

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

input:

2
22

output:

12

result:

ok 1 number(s): "12"

Test #5:

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

input:

2
21

output:

2

result:

ok 1 number(s): "2"

Test #6:

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

input:

3
233

output:

10

result:

ok 1 number(s): "10"

Test #7:

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

input:

3
666

output:

54

result:

ok 1 number(s): "54"

Test #8:

score: 0
Accepted
time: 360ms
memory: 647476kb

input:

1000000
3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...

output:

496166704

result:

ok 1 number(s): "496166704"

Test #9:

score: -100
Memory Limit Exceeded

input:

3000000
2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...

output:

890701718

result: