QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397653 | #5440. P-P-Palindrome | Diu | WA | 140ms | 62520kb | C++14 | 1.8kb | 2024-04-24 15:39:07 | 2024-04-24 15:39:07 |
Judging History
answer
//
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,bas=131,mod=998244353;
int n;
char s[N];
int hs1[N],hs2[N],t[N],inv[N],ip[N];
map<int,int> mp1[N],mp2;
int qpow(int x,int y=mod-2){
int m=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)m=1ll*m*x%mod;
return m;
}
int Hs1(int l,int r){
return (hs1[r]-1ll*hs1[l-1]*t[r-l+1]%mod+mod)%mod;
}
int Hs2(int l,int r){
return 1ll*(hs2[r]-hs2[l-1]+mod)%mod*inv[l-1]%mod;
}
bool chk(int l,int r){
return Hs1(l,r)==Hs2(l,r);
}
signed main(){
scanf("%d",&n);
t[0]=1;
for(int i=1;i<N;i++)t[i]=1ll*t[i-1]*bas%mod;
inv[N-1]=qpow(t[N-1]);
for(int i=N-2;i>=0;i--)inv[i]=1ll*inv[i+1]*bas%mod;
for(int i=1;i<N;i++)ip[i]=qpow(1+mod-t[i]);
ll ans=0;
for(;n--;){
scanf("\n%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++)hs1[i]=(1ll*bas*hs1[i-1]+s[i])%mod;
for(int i=1;i<=len;i++)hs2[i]=(hs2[i-1]+1ll*t[i-1]*s[i])%mod;
for(int i=1;i<=len;i++){
int l=0,r=min(i-1,len-i)+1;
while(l+1<r){
int mid=l+r>>1;
if(chk(i-mid,i+mid))l=mid;
else r=mid;
}
// printf("Odd:%d %d\n",i,l);
for(;l>=0;l--){
int h=Hs1(i-l,i+l);
if(mp1[2*l+1][h])break;
// printf("%d %d\n",i-l,i+l);
mp1[2*l+1][h]=1;
int val=1ll*h*ip[2*l]%mod;
int res=++mp2[val];
ans+=1ll*res*res,ans-=1ll*(res-1)*(res-1);
}
}
for(int i=1;i<len;i++){
int l=-1,r=min(i-1,len-i-1)+1;
while(l+1<r){
int mid=l+r>>1;
if(chk(i-mid,i+1+mid))l=mid;
else r=mid;
}
// printf("Even:%d %d\n",i,l);
for(;l>=0;l--){
int h=Hs1(i-l,i+1+l);
if(mp1[2*l+2][h])break;
// printf("%d %d\n",i-l,i+1+l);
mp1[2*l+2][h]=1;
int val=1ll*h*ip[2*l+2]%mod;
int res=++mp2[val];
ans+=1ll*res*res,ans-=1ll*(res-1)*(res-1);
}
}
}
printf("%lld\n",ans);
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 140ms
memory: 62520kb
input:
2 aaaa aaa
output:
6
result:
wrong answer 1st numbers differ - expected: '16', found: '6'