QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#151588 | #5440. P-P-Palindrome | TadijaSebez | WA | 7ms | 12512kb | C++14 | 1.9kb | 2023-08-27 04:27:36 | 2023-08-27 04:27:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
const int N=1000050;
const int base=37;
int po[N];
char s[N];
int img,zero,tsz,go[N][26],link[N],len[N];
int hsh[N];
void init(){
img=++tsz;
zero=++tsz;
len[img]=-1;
len[zero]=0;
link[zero]=img;
link[img]=img;
po[0]=1;
for(int i=1;i<N;i++){
po[i]=mul(po[i-1],base);
}
}
set<pair<int,int>> all;
void DFS(int u){
if(len[u]>0){
all.insert({len[u],hsh[u]});
}
for(int i=0;i<26;i++){
if(go[u][i]){
hsh[go[u][i]]=add(add(i+1,mul(i+1,po[len[u]+1])),mul(hsh[u],base));
DFS(go[u][i]);
}
}
}
int main(){
int n;
scanf("%i",&n);
init();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int m=strlen(s+1);
int curr=zero;
for(int j=1;j<=m;j++){
while(j-len[curr]-1<=0 || s[j]!=s[j-len[curr]-1]){
curr=link[curr];
}
int next=go[curr][s[j]-'a'];
if(next==0){
next=++tsz;
go[curr][s[j]-'a']=next;
len[next]=len[curr]+2;
int up=link[curr];
while(up!=img && go[up][s[j]-'a']==0){
up=link[up];
}
if(go[up][s[j]-'a']!=0 && len[next]!=1){
link[next]=go[up][s[j]-'a'];
}else{
link[next]=zero;
}
}
curr=next;
}
}
hsh[zero]=0;
DFS(zero);
for(int i=0;i<26;i++){
if(go[img][i]!=0){
hsh[go[img][i]]=i+1;
DFS(go[img][i]);
}
}
ll ans=0;
while(all.size()){
int len=all.begin()->first;
int hsh=all.begin()->second;
int len1=len;
int hsh1=hsh;
int cnt=0;
while(true){
if(all.count({len1,hsh1})){
cnt++;
all.erase({len1,hsh1});
len1+=len;
hsh1=add(hsh,mul(po[len],hsh1));
}else{
break;
}
}
ans+=(ll)cnt*cnt;
}
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 12292kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 7ms
memory: 12428kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 1ms
memory: 11840kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 12512kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1272
result:
wrong answer 1st numbers differ - expected: '1282', found: '1272'