QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#331712 | #7876. Cyclic Substrings | ucup-team093 | AC ✓ | 103ms | 313812kb | C++20 | 1.1kb | 2024-02-18 17:37:28 | 2024-02-18 17:37:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 6e6 + 10, P = 998244353;
int trie[N][10], nxt[N], len[N], cnt[N], cv = 2;
int sum[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
string s;
cin >> n >> s;
s = "#" + s + s;
nxt[1] = 1;
len[1] = -1;
nxt[2] = 1;
len[2] = 0;
for(int i = 1, j = 2; i < s.size(); i ++) {
while(s[i] != s[i - len[j] - 1]) j = nxt[j];
if(!trie[j][s[i] - '0']) {
trie[j][s[i] - '0'] = ++ cv;
len[cv] = len[j] + 2;
for(int &k = (nxt[cv] = nxt[j]); s[i] != s[i - len[k] - 1]; k = nxt[k]);
if(nxt[cv] != j) nxt[cv] = trie[nxt[cv]][s[i] - '0'];
else nxt[cv] = 2;
}
j = trie[j][s[i] - '0'];
if(i > n) cnt[j] ++;
}
int ans = 0;
for(int i = cv; i > 1; i --) {
(cnt[nxt[i]] += cnt[i]) %= P;
if(len[i] <= n) ans = (ans + (long long)(cnt[i] - sum[i] + P) * (cnt[i] - sum[i] + P) % P * len[i]) % P;
}
cout << ans;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9720kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9636kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 1ms
memory: 9632kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9788kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 0ms
memory: 9760kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 2ms
memory: 9756kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 0ms
memory: 9740kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 31ms
memory: 112292kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: 0
Accepted
time: 80ms
memory: 313776kb
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
output:
890701718
result:
ok 1 number(s): "890701718"
Test #10:
score: 0
Accepted
time: 71ms
memory: 151980kb
input:
3000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
224009870
result:
ok 1 number(s): "224009870"
Test #11:
score: 0
Accepted
time: 76ms
memory: 313752kb
input:
3000000 8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...
output:
51985943
result:
ok 1 number(s): "51985943"
Test #12:
score: 0
Accepted
time: 80ms
memory: 313812kb
input:
3000000 1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...
output:
355676465
result:
ok 1 number(s): "355676465"
Test #13:
score: 0
Accepted
time: 103ms
memory: 280564kb
input:
3000000 7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...
output:
788510374
result:
ok 1 number(s): "788510374"
Test #14:
score: 0
Accepted
time: 95ms
memory: 291792kb
input:
3000000 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555...
output:
691884476
result:
ok 1 number(s): "691884476"
Test #15:
score: 0
Accepted
time: 59ms
memory: 167420kb
input:
3000000 0990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990...
output:
701050848
result:
ok 1 number(s): "701050848"
Test #16:
score: 0
Accepted
time: 40ms
memory: 60724kb
input:
3000000 2772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772...
output:
486861605
result:
ok 1 number(s): "486861605"
Test #17:
score: 0
Accepted
time: 89ms
memory: 269776kb
input:
3000000 4554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554...
output:
450625621
result:
ok 1 number(s): "450625621"
Test #18:
score: 0
Accepted
time: 78ms
memory: 265608kb
input:
3000000 1181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181...
output:
649551870
result:
ok 1 number(s): "649551870"
Extra Test:
score: 0
Extra Test Passed