QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#198846 | #5440. P-P-Palindrome | UrgantTeam | WA | 237ms | 137968kb | C++23 | 3.2kb | 2023-10-03 17:47:07 | 2023-10-03 17:47:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7, P = 29;
int const maxn = 1e6 + 5;
ll p[maxn], rev[maxn], h[maxn];
vector < pair < int, int > > palindromes;
int len[maxn];
set < ll > used[maxn];
vector < ll > open[maxn];
ll st(ll x, ll y) {
if (y == 0) return 1;
if (y % 2 == 0) return st(x * x % mod, y / 2);
return x * st(x, y - 1) % mod;
}
inline ll get(int l, int r) {
return (h[r] - h[l - 1] + mod) * rev[l - 1] % mod;
}
void manaker_odd(string s) {
int l = 0, r = 0, n = s.size();
for (int i = 1; i < n; i++) {
if (i <= r) len[i] = min(r - i + 1, len[l + r - i]);
else len[i] = 0;
while (i - len[i] > 0 && i + len[i] < n && s[i - len[i]] == s[i + len[i]]) {
palindromes.push_back({i - len[i], i + len[i]});
len[i]++;
}
if (i + len[i] - 1 > r) {
r = i + len[i] - 1;
l = i - len[i] + 1;
}
}
}
void manaker_even(string s) {
int l = 0, r = 0, n = s.size();
for (int i = 2; i < n; i++) {
if (i <= r) len[i] = min(r - i + 1, len[l + r - i]);
else len[i] = 0;
while (i - len[i] - 1 > 0 && i + len[i] < n && s[i - len[i] - 1] == s[i + len[i]]) {
palindromes.push_back({i - len[i] - 1, i + len[i]});
len[i]++;
}
if (i + len[i] - 1 > r) {
r = i + len[i] - 1;
l = i - len[i];
}
}
}
main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#endif // HOME
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
p[0] = 1, rev[0] = 1;
for (int i = 1; i < maxn; i++) p[i] = p[i - 1] * P % mod;
rev[maxn - 1] = st(p[maxn - 1], mod - 2);
for (int i = maxn - 2; i >= 1; i--) rev[i] = rev[i + 1] * P % mod;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
int len = s.size();
s = "#" + s;
for (int j = 1; j <= len; j++) {
h[j] = (h[j - 1] + (s[j] - 'a' + 1) * p[j - 1]) % mod;
}
palindromes = {};
manaker_even(s);
manaker_odd(s);
for (auto key : palindromes) used[key.second - key.first + 1].insert(get(key.first, key.second));
}
for (int i = 1; i < maxn; i++) {
for (auto key : used[i]) {
open[i].push_back(key);
}
}
set < ll > bad;
__int128 ans = 0;
for (int len = 1; len < maxn; len++) {
for (auto key : open[len]) {
if (bad.find(key) != bad.end()) continue;
int cur_len = 0;
ll cur_h = 0;
while (1) {
cur_h = (cur_h * p[len] + key) % mod;
if (used[cur_len + len].find(cur_h) == used[cur_len + len].end()) break;
cur_len += len;
bad.insert(cur_h);
}
ll cnt = cur_len / len;
ans += cnt * cnt;
}
}
string out = "";
while (ans) {
out += char('0' + ans % 10);
ans /= 10;
}
if (out.empty()) out = "0";
else reverse(out.begin(), out.end());
cout << out << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 26ms
memory: 95168kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 28ms
memory: 93088kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 24ms
memory: 93140kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 28ms
memory: 92972kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 68ms
memory: 101392kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 64ms
memory: 101496kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: -100
Wrong Answer
time: 237ms
memory: 137968kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
309906
result:
wrong answer 1st numbers differ - expected: '133586', found: '309906'