QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398240 | #5440. P-P-Palindrome | nKessi | WA | 71ms | 122984kb | C++14 | 2.7kb | 2024-04-25 09:27:01 | 2024-04-25 09:27:02 |
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;
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];
uLL P[MAXN];
vector <uLL> Hash[MAXN];
map <uLL, 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);
}
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;
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;
}
}
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: 11ms
memory: 93356kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 8ms
memory: 92808kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 22ms
memory: 92596kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 8ms
memory: 92732kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 31ms
memory: 106900kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 16ms
memory: 108184kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: 0
Accepted
time: 71ms
memory: 121676kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133586
result:
ok 1 number(s): "133586"
Test #8:
score: 0
Accepted
time: 67ms
memory: 118832kb
input:
3 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...
output:
118967
result:
ok 1 number(s): "118967"
Test #9:
score: 0
Accepted
time: 64ms
memory: 117120kb
input:
3 bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...
output:
114444
result:
ok 1 number(s): "114444"
Test #10:
score: 0
Accepted
time: 65ms
memory: 118140kb
input:
3 abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...
output:
115321
result:
ok 1 number(s): "115321"
Test #11:
score: 0
Accepted
time: 70ms
memory: 122984kb
input:
3 azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...
output:
131825
result:
ok 1 number(s): "131825"
Test #12:
score: 0
Accepted
time: 24ms
memory: 94728kb
input:
3 yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...
output:
6
result:
ok 1 number(s): "6"
Test #13:
score: 0
Accepted
time: 7ms
memory: 95092kb
input:
3 azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...
output:
6
result:
ok 1 number(s): "6"
Test #14:
score: 0
Accepted
time: 15ms
memory: 95876kb
input:
3 byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...
output:
6
result:
ok 1 number(s): "6"
Test #15:
score: -100
Wrong Answer
time: 27ms
memory: 111128kb
input:
1 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...
output:
201946
result:
wrong answer 1st numbers differ - expected: '113382', found: '201946'