QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397723 | #5440. P-P-Palindrome | Diu | WA | 721ms | 208188kb | C++14 | 2.5kb | 2024-04-24 16:18:51 | 2024-04-24 16:18:51 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10,mod1=998244353,mod2=1e9+7;
int n;
char s[N];
struct node{
int x,y;
node(int xx=0,int yy=0){x=xx,y=yy;}
ll v(){return 1ll*x*mod2+y;}
bool operator==(const node t)const{return x==t.x&&y==t.y;}
};
const node bas={131,151};
node operator+(node a,node b){
return {(a.x+b.x)%mod1,(a.y+b.y)%mod2};
}
node operator-(node a,node b){
return {(a.x-b.x+mod1)%mod1,(a.y-b.y+mod2)%mod2};
}
node operator*(node a,node b){
return {1ll*a.x*b.x%mod1,1ll*a.y*b.y%mod2};
}
node hs1[N],hs2[N],t[N],inv[N],p[N],ip[N];
map<ll,int> mp1[N],mp2;
int qpow(int x,int y,int mod){
int m=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)m=1ll*m*x%mod;
return m;
}
node Hs1(int l,int r){
return hs1[r]-(hs1[l-1]*t[r-l+1]);
}
node Hs2(int l,int r){
return (hs2[r]-hs2[l-1])*inv[l-1];
}
bool chk(int l,int r){
return Hs1(l,r)==Hs2(l,r);
}
const int L=2e6;
node calc(int l,int r){
int d=r-l+1,v=L/d;
return (Hs1(l,r)*ip[d]*p[d*v])+(Hs1(l,l+(L-d*v)-1)*t[d*v]);
}
signed main(){
scanf("%d",&n);
t[0]=1;
for(int i=1;i<N;i++)t[i]=t[i-1]*bas;
inv[N-1].x=qpow(t[N-1].x,mod1-2,mod1);
inv[N-1].y=qpow(t[N-1].y,mod2-2,mod2);
for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*bas;
for(int i=1;i<N;i++){
p[i].x=1+mod1-t[i].x;
p[i].y=1+mod1-t[i].y;
ip[i].x=qpow(1+mod1-t[i].x,mod1-2,mod1);
ip[i].y=qpow(1+mod2-t[i].y,mod2-2,mod2);
}
ll ans=0;
for(;n--;){
scanf("\n%s",s+1);
int len=strlen(s+1);
for(int i=1;i<=len;i++)hs1[i]=(bas*hs1[i-1])+s[i];
for(int i=1;i<=len;i++)hs2[i]=hs2[i-1]+(t[i-1]*s[i]);
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--){
node h=Hs1(i-l,i+l);
if(mp1[2*l+1][h.v()])break;
// printf("%d %d\n",i-l,i+l);
mp1[2*l+1][h.v()]=1;
node val=calc(i-l,i+l);
int res=++mp2[val.v()];
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--){
node h=Hs1(i-l,i+1+l);
if(mp1[2*l+2][h.v()])break;
// printf("%d %d\n",i-l,i+1+l);
mp1[2*l+2][h.v()]=1;
node val=calc(i-l,i+1+l);
int res=++mp2[val.v()];
ans+=1ll*res*res,ans-=1ll*(res-1)*(res-1);
}
}
}
printf("%lld\n",ans);
}
详细
Test #1:
score: 100
Accepted
time: 523ms
memory: 191276kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 541ms
memory: 191324kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 535ms
memory: 191468kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 532ms
memory: 191400kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 646ms
memory: 195216kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 651ms
memory: 195264kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: -100
Wrong Answer
time: 721ms
memory: 208188kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133580
result:
wrong answer 1st numbers differ - expected: '133586', found: '133580'