QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#665811 | #5440. P-P-Palindrome | qvzeyang | WA | 20ms | 92956kb | C++23 | 2.3kb | 2024-10-22 15:24:44 | 2024-10-22 15:24:50 |
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;
pr bl;
if(!belong.count(now)){
belong[now]=now;
bl=now;
now=getnext(now,bl);
while(p[now.second].count(now.first)){
belong[now]=bl;
now=getnext(now,bl);
}
}
bl=belong[now];
num[bl]++;
}
}
for(auto it=num.begin();it!=num.end();it++)ans+=(*it).second*(*it).second;
cout<<ans;
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 20ms
memory: 92956kb
input:
2 aaaa aaa
output:
10
result:
wrong answer 1st numbers differ - expected: '16', found: '10'