QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#771372 | #5440. P-P-Palindrome | ucup-team3702# | WA | 33ms | 73324kb | C++20 | 2.4kb | 2024-11-22 12:15:50 | 2024-11-22 12:15:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define pv(a) cout << #a" = " << a << endl
#define pa(a, l, r) cout << #a" : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]
using i64 = long long;
const int P = 998244353;
const int base1 = 131;
const int base2 = 13331;
const int N = 1e6 + 10;
int inc(int a, int b) {
return (a += b) >= P ? a - P : a;
}
int dec(int a, int b) {
return (a -= b) < 0 ? a + P : a;
}
int mul(int a, int b) {
return (i64) a * b % P;
}
int n, m, pw1[N], pw2[N];
char s[N];
i64 ans;
struct str {
char *s;
int pre1[N], pre2[N];
void init(char *_s) {
s = _s, m = strlen(s + 1);
rep(i, 1, m) {
pre1[i] = inc(mul(pre1[i - 1], base1), s[i] - 'a' + 1);
pre2[i] = inc(mul(pre2[i - 1], base2), s[i] - 'a' + 1);
}
}
pair <int, int> calc(int l, int r) {
int res1 = dec(pre1[r], mul(pre1[l - 1], pw1[r - l + 1]));
int res2 = dec(pre2[r], mul(pre2[l - 1], pw2[r - l + 1]));
return make_pair(res1, res2);
}
} cur;
set <pair <int, int>> f[N];
int d[2 * N];
char t[2 * N];
void manacher() {
rep(i, 1, 2 * m + 1) t[i] = i & 1 ? '#' : s[i >> 1];
for (int l = 0, r = -1, i = 1; i <= 2 * m + 1; ++i) {
d[i] = i <= r ? min(r - i + 1, d[l + r - i]) : 1;
while (i - d[i] > 0 && i + d[i] <= 2 * m + 1 && t[i + d[i]] == t[i - d[i]]) {
if (!(i - d[i] & 1)) {
f[d[i] + 1].insert(cur.calc((i - d[i]) / 2, (i + d[i]) / 2));
}
++d[i];
}
if (i + d[i] > r) l = i - d[i], r = i + d[i];
}
}
int main() {
pw1[0] = pw2[0] = 1;
rep(i, 1, N - 5) {
pw1[i] = mul(pw1[i - 1], base1);
pw2[i] = mul(pw2[i - 1], base2);
}
scanf("%d", &n);
rep(i, 1, n) {
scanf("%s", s + 1);
cur.init(s);
manacher();
}
rep(i, 1, N - 5) {
int coef1 = pw1[i], coef2 = pw2[i];
for (auto it : f[i]) {
int cnt = 1, val1, val2;
tie(val1, val2) = it;
int res1 = val1, res2 = val2;
for (int j = i + i; j <= N - 5; j += i) {
res1 = inc(mul(res1, coef1), val1);
res2 = inc(mul(res2, coef2), val2);
auto fk = make_pair(res1, res2);
if (f[j].find(fk) != f[j].end()) {
++cnt;
f[j].erase(fk);
} else {
break;
}
}
ans += (i64) cnt * cnt;
}
}
printf("%lld\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 12ms
memory: 64104kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 15ms
memory: 65212kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 11ms
memory: 62888kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 11ms
memory: 64896kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 20ms
memory: 68520kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 24ms
memory: 65852kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: 0
Accepted
time: 31ms
memory: 70064kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133586
result:
ok 1 number(s): "133586"
Test #8:
score: 0
Accepted
time: 30ms
memory: 69840kb
input:
3 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...
output:
118967
result:
ok 1 number(s): "118967"
Test #9:
score: 0
Accepted
time: 25ms
memory: 73224kb
input:
3 bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...
output:
114444
result:
ok 1 number(s): "114444"
Test #10:
score: 0
Accepted
time: 26ms
memory: 73324kb
input:
3 abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...
output:
115321
result:
ok 1 number(s): "115321"
Test #11:
score: 0
Accepted
time: 21ms
memory: 71704kb
input:
3 azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...
output:
131825
result:
ok 1 number(s): "131825"
Test #12:
score: -100
Wrong Answer
time: 33ms
memory: 67264kb
input:
3 yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...
output:
99328
result:
wrong answer 1st numbers differ - expected: '6', found: '99328'