QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#642615 | #7876. Cyclic Substrings | ucup-team1001 | AC ✓ | 372ms | 555152kb | C++20 | 2.5kb | 2024-10-15 15:18:57 | 2024-10-15 15:18:57 |
Judging History
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