QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#273860 | #7876. Cyclic Substrings | ucup-team2000# | AC ✓ | 267ms | 914680kb | C++20 | 1.9kb | 2023-12-03 04:48:10 | 2023-12-03 04:48:10 |
Judging History
answer
#include <bits/stdc++.h>
template<int MAXN = 4500000, int MAXC = 10>
struct palindromic_tree {
struct node {
node *child[MAXC], *fail; int len;
node(int len = 0) : fail(NULL), len(len) {
memset(child, NULL, sizeof(child)); }
} node_pool[MAXN * 2], *tot_node;
int size, text[MAXN * 2];
node *odd, *even, *last;
node *match(node *now) {
for (; text[size - now -> len - 1] != text[size]; now = now -> fail);
return now; }
bool extend(int token) {
text[++size] = token; node *now = match(last);
if (now -> child[token])
return last = now -> child[token], false;
if (tot_node == node_pool + MAXN * 2) while (true);
last = now -> child[token] = new (tot_node++) node(now -> len + 2);
if (now == odd) last -> fail = even;
else {
now = match(now -> fail);
last -> fail = now -> child[token]; }
return true; }
void init() {
text[size = 0] = -1; tot_node = node_pool;
last = even = new(tot_node++) node(0); odd = new(tot_node++) node(-1);
even -> fail = odd; }
palindromic_tree() { init(); } };
const int MOD = 998244353;
const int MAXN = 4500000;
palindromic_tree<> _p;
int N;
char str[3000001];
int sum1[MAXN * 2], sum2[MAXN * 2];
int main() {
scanf("%d", &N);
scanf(" %s", str);
for (int i = 0; i < N; ++i) {
_p.extend(str[i] - '0');
++sum1[_p.last - _p.node_pool];
++sum2[_p.last - _p.node_pool];
}
for (int i = _p.tot_node - _p.node_pool - 1; i >= 0; --i) {
if (_p.node_pool[i].fail)
sum1[_p.node_pool[i].fail - _p.node_pool] += sum1[i];
}
for (int i = 0; i < N; ++i) {
_p.extend(str[i] - '0');
++sum2[_p.last - _p.node_pool];
}
int ans2 = 0;
for (int i = _p.tot_node - _p.node_pool - 1; i >= 0; --i) {
if (_p.node_pool[i].fail)
sum2[_p.node_pool[i].fail - _p.node_pool] += sum2[i];
int f = _p.node_pool[i].len;
if (f > 0 && f <= N) {
ans2 = (ans2 + 1ll * (sum2[i] - sum1[i]) * (sum2[i] - sum1[i]) % MOD * f) % MOD;
}
}
printf("%d\n", ans2);
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 36ms
memory: 853488kb
input:
5 01010
output:
39
result:
ok 1 number(s): "39"
Test #2:
score: 0
Accepted
time: 54ms
memory: 853604kb
input:
8 66776677
output:
192
result:
ok 1 number(s): "192"
Test #3:
score: 0
Accepted
time: 43ms
memory: 853488kb
input:
1 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 59ms
memory: 853776kb
input:
2 22
output:
12
result:
ok 1 number(s): "12"
Test #5:
score: 0
Accepted
time: 59ms
memory: 853552kb
input:
2 21
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 40ms
memory: 853552kb
input:
3 233
output:
10
result:
ok 1 number(s): "10"
Test #7:
score: 0
Accepted
time: 52ms
memory: 853560kb
input:
3 666
output:
54
result:
ok 1 number(s): "54"
Test #8:
score: 0
Accepted
time: 111ms
memory: 872380kb
input:
1000000 3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333...
output:
496166704
result:
ok 1 number(s): "496166704"
Test #9:
score: 0
Accepted
time: 251ms
memory: 914680kb
input:
3000000 2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222...
output:
890701718
result:
ok 1 number(s): "890701718"
Test #10:
score: 0
Accepted
time: 240ms
memory: 897372kb
input:
3000000 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999...
output:
224009870
result:
ok 1 number(s): "224009870"
Test #11:
score: 0
Accepted
time: 229ms
memory: 913432kb
input:
3000000 8989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989898989...
output:
51985943
result:
ok 1 number(s): "51985943"
Test #12:
score: 0
Accepted
time: 216ms
memory: 914632kb
input:
3000000 1911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911911...
output:
355676465
result:
ok 1 number(s): "355676465"
Test #13:
score: 0
Accepted
time: 251ms
memory: 907428kb
input:
3000000 7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777...
output:
788510374
result:
ok 1 number(s): "788510374"
Test #14:
score: 0
Accepted
time: 267ms
memory: 910324kb
input:
3000000 5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555...
output:
691884476
result:
ok 1 number(s): "691884476"
Test #15:
score: 0
Accepted
time: 159ms
memory: 903052kb
input:
3000000 0990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990990909909909099090990990909909909099090990990909909099099090990990909909099099090990990909909099099090990909909909099099090990909909909099090990...
output:
701050848
result:
ok 1 number(s): "701050848"
Test #16:
score: 0
Accepted
time: 127ms
memory: 887252kb
input:
3000000 2772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772772727727727277272772772727727727277272772772727727277277272772772727727277277272772772727727277277272772727727727277277272772727727727277272772...
output:
486861605
result:
ok 1 number(s): "486861605"
Test #17:
score: 0
Accepted
time: 205ms
memory: 905452kb
input:
3000000 4554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554554545545545455454554554545545545455454554554545545455455454554554545545455455454554554545545455455454554545545545455455454554545545545455454554...
output:
450625621
result:
ok 1 number(s): "450625621"
Test #18:
score: 0
Accepted
time: 209ms
memory: 907740kb
input:
3000000 1181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181811811818118181181181811818118118181181181811818118118181181181811818118118181181811811818118118181181811811818118181181181811811818118181181181...
output:
649551870
result:
ok 1 number(s): "649551870"
Extra Test:
score: 0
Extra Test Passed