QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#397687#5440. P-P-PalindromeDiuWA 451ms106640kbC++142.3kb2024-04-24 15:55:232024-04-24 15:55:26

Judging History

你现在查看的是最新测评结果

  • [2024-04-24 15:55:26]
  • 评测
  • 测评结果:WA
  • 用时:451ms
  • 内存:106640kb
  • [2024-04-24 15:55:23]
  • 提交

answer

// 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10,bas=131,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;}
};
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],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);
}
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++){
		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=h*ip[2*l+1];
				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=h*ip[2*l+2];
				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: 266ms
memory: 89772kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 269ms
memory: 89772kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 257ms
memory: 89952kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 264ms
memory: 89848kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 383ms
memory: 93648kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 379ms
memory: 93656kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 451ms
memory: 106640kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133610

result:

wrong answer 1st numbers differ - expected: '133586', found: '133610'