QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#238636 | #5440. P-P-Palindrome | Network_Error | WA | 8ms | 17884kb | C++14 | 1.6kb | 2023-11-04 17:10:22 | 2023-11-04 17:10:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
#define int long long
int n, r, s[1000010], ans;
unsigned int hsh[1000010], bpw[1000010]; const int base = 29, mod = 100000000000000049; map<unsigned int, int> p;
int tot, lst, tr[1000010][26], bor[1000010], len[1000010];
void init() {
tot = 1; len[1] = -1; bor[0] = 1;
}
unsigned int gethsh(int l, int r) {
return (hsh[r] + mod - hsh[l - 1] * bpw[r - l + 1] % mod) % mod;
}
void extend(int c) {
s[++r] = c + 1;
int u = lst;
while (s[r] != s[r - len[u] - 1]) u = bor[u];
if (!tr[u][c]) {
int v = ++tot; len[v] = len[u] + 2; bor[v] = bor[u];
while (s[r] != s[r - len[bor[v]] /*shaber mistake*/ - 1]) bor[v] = bor[bor[v]];
bor[v] = tr[bor[v]][c]; tr[u][c] = v;
// 求 v 的最小整周期
int d = len[v];
if (len[v] % (len[v] - len[bor[v]]) == 0) d = len[v] - len[bor[v]];
ans += p[gethsh(r - d + 1, r)]; p[gethsh(r - d + 1, r)]++;
} lst = tr[u][c];
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
bpw[0] = 1; for (int i = 1; i <= 1e6; i++) bpw[i] = bpw[i - 1] * base % mod;
cin >> n;
init();
for (int i = 1; i <= n; i++) {
r = lst = 0;
string s; cin >> s;
hsh[0] = 1;
for (int i = 0; i < s.size(); i++) {
hsh[i + 1] = (hsh[i] * base + s[i] - 'a' + 1) % mod; extend(s[i] - 'a');
}
} cout << ans * 2 + tot - 1 << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 17696kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 0ms
memory: 17768kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 3ms
memory: 17884kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 17864kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1272
result:
wrong answer 1st numbers differ - expected: '1282', found: '1272'