QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665798 | #5440. P-P-Palindrome | qvzeyang | TL | 24ms | 95088kb | C++23 | 2.3kb | 2024-10-22 15:19:54 | 2024-10-22 15:21:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pr pair<int,int>
#define _(x,y) x=(x+y)%mod
#define ll long long
#define int long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
const int mod=998244353,base=31;
int n,ans;
string s[1000100];
int len[1000100],pw[1001000];
vector<int>ha[1000100][2];
map<int,pr>p[1000100];
map<pr,pr>belong;
map<pr,int>num;
int gethash(int x,int ty,int l,int r){return (ha[x][ty][r]-ha[x][ty][l-1]*pw[r-l+1]%mod+mod)%mod;}
void getstring(int x,int l,int r){
if(l>r)return;
int has=gethash(x,0,l,r);
if(p[r-l+1].count(has))return;
p[r-l+1][has]=pr(has,r-l+1);
getstring(x,l+1,r-1);
}
pr getnext(pr now,pr bl){
now.second+=bl.second;
now.first=(now.first*pw[bl.second]+bl.first)%mod;
return now;
}
signed main(){
pw[0]=1;for(int i=1;i<=1000000;i++)pw[i]=pw[i-1]*base%mod;
n=read();
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]=' '+s[i];
len[i]=s[i].length()-1;
ha[i][0].resize(len[i]+2);
ha[i][1].resize(len[i]+2);
for(int j=1;j<=len[i];j++){
ha[i][0][j]=(ha[i][0][j-1]*base+s[i][j]-'a'+1)%mod;
ha[i][1][j]=(ha[i][1][j-1]*base+s[i][len[i]-j+1]-'a'+1)%mod;
}for(int j=1;j<=len[i];j++){
int l,r,lenth;
l=1,r=min(j,len[i]-j+1),lenth=0;
while(l<=r){
int mid=(l+r)/2;
if(gethash(i,0,j-mid+1,j)==gethash(i,1,len[i]-(j+mid-1)+1,len[i]-j+1))lenth=mid,l=mid+1;
else r=mid-1;
}getstring(i,j-lenth+1,j+lenth-1);
if(j!=len[i] and s[i][j]==s[i][j+1]){
l=1,r=min(j,len[i]-j),lenth=0;
while(l<=r){
int mid=(l+r)/2;
if(gethash(i,0,j-mid+1,j)==gethash(i,1,len[i]-(j+mid)+1,len[i]-j))lenth=mid,l=mid+1;
else r=mid-1;
}getstring(i,j-lenth+1,j+lenth);
}
}
}
for(int i=1;i<=1000000;i++){
for(auto it=p[i].begin();it!=p[i].end();it++){
pr now=(*it).second;
if(!belong.count(now))belong[now]=now;
pr bl=belong[now];
num[bl]++;
now=getnext(now,bl);
while(p[now.second].count(now.first)){
belong[now]=bl;
now=getnext(now,bl);
}
}
}
for(auto it=num.begin();it!=num.end();it++)ans+=(*it).second*(*it).second;
cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 24ms
memory: 92908kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 20ms
memory: 95088kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 15ms
memory: 93056kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 19ms
memory: 93232kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: -100
Time Limit Exceeded
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...