QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398244 | #5440. P-P-Palindrome | nKessi | WA | 76ms | 119140kb | C++14 | 2.8kb | 2024-04-25 09:29:13 | 2024-04-25 09:29:14 |
Judging History
answer
/*
世界の果てさえ
【世界的尽头在何处】
仆らは知らない
【我们也无从知晓】
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <random>
#include <ctime>
#include <string>
#include <iostream>
#define pr pair <int, int>
#define mr make_pair
#define LL long long
#define ls tree[p].L
#define rs tree[p].R
#define uLL unsigned long long
using namespace std;
const int MAXN = 1e6 + 5, Mod = 1e9 + 7;
struct node {
int son[27], fail, len, id, ed;
}pam[MAXN];
int n, las = 1, tot = 1, mb1, mb2, c[MAXN];
vector <int> v[MAXN];
string s[MAXN];
LL P[MAXN];
vector <LL> Hash[MAXN];
map <LL, int> mp;
void read(int &x) {
x = 0; bool f = 1; char C = getchar();
for(; C < '0' || C > '9'; C = getchar()) if(C == '-') f = 0;
for(; C >= '0' && C <= '9'; C = getchar()) x = (x << 1) + (x << 3) + (C ^ 48);
x = (f ? x : -x);
}
int getfail(int x) {
while(s[mb1][mb2] != s[mb1][mb2 - pam[x].len - 1]) x = pam[x].fail;
return x;
}
void ins(int x) {
int p = getfail(las), now = pam[p].son[x];
if(!now) {
now = ++ tot; pam[now].len = pam[p].len + 2;
pam[now].fail = pam[getfail(pam[p].fail)].son[x]; pam[p].son[x] = now;
pam[tot].id = mb1; pam[tot].ed = mb2;
}
las = now; c[las] ++;
}
void dfs(int x) {
for(auto y : v[x]) {
dfs(y);
c[x] += c[y]; //printf("?%d %d %d?\n", x, y, pam[y].len);
if(pam[y].id) pam[x].id = pam[y].id, pam[x].ed = pam[y].ed;
}
}
uLL gethash(int id, int l, int r) {
return ((Hash[id][r] - (l ? Hash[id][l - 1] * P[r - l + 1] : 0)) % Mod + Mod) % Mod;
}
int main() {
read(n); pam[0].len = 0; pam[1].len = -1; pam[0].fail = pam[1].fail = 1; P[0] = 1;
for(int i = 1; i <= 1000000; i ++) P[i] = P[i - 1] * 2007391 % Mod;
for(int i = 1; i <= n; i ++) {
cin >> s[i]; las = 1; mb1 = i; Hash[i].resize(s[i].length());
for(int j = 0; j < s[i].length(); j ++) mb2 = j, ins(s[i][j] - 'a');
for(int j = 0; j < s[i].length(); j ++) {
Hash[i][j] = s[i][j];
if(j) Hash[i][j] += Hash[i][j - 1] * 2007391, Hash[i][j] %= Mod;
}
}
v[1].emplace_back(0);
for(int i = 2; i <= tot; i ++) v[pam[i].fail].emplace_back(i);
dfs(1);
for(int i = 2; i <= tot; i ++) {
// if(c[i] != n) continue;
// printf("|%d %d|\n", i, pam[i].len);
if(pam[i].len == 1) {
mp[gethash(pam[i].id, pam[i].ed, pam[i].ed)] ++; continue;
}
int len1 = pam[i].len, len2 = pam[pam[i].fail].len;
if(len1 % (len1 - len2) == 0) {
mp[gethash(pam[i].id, pam[i].ed - (len1 - len2) + 1, pam[i].ed)] ++;
}
else mp[gethash(pam[i].id, pam[i].ed - len1 + 1, pam[i].ed)] ++;
}
LL ans = 0;
for(auto i : mp) ans += 1ll * i.second * i.second;//, printf("?%d?", i.second);
printf("%lld", ans);
return 0;
}
/*
2
aaaa
aaa
*/
详细
Test #1:
score: 100
Accepted
time: 21ms
memory: 91568kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 21ms
memory: 89788kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 12ms
memory: 89744kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 13ms
memory: 89800kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 33ms
memory: 104824kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 31ms
memory: 104936kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: -100
Wrong Answer
time: 76ms
memory: 119140kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133608
result:
wrong answer 1st numbers differ - expected: '133586', found: '133608'