QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#274700 | #7876. Cyclic Substrings | ucup-team2307# | ML | 360ms | 647476kb | C++20 | 1.7kb | 2023-12-03 20:19:49 | 2023-12-03 20:19:49 |
Judging History
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