QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#665811#5440. P-P-PalindromeqvzeyangWA 20ms92956kbC++232.3kb2024-10-22 15:24:442024-10-22 15:24:50

Judging History

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

  • [2024-10-22 15:24:50]
  • 评测
  • 测评结果:WA
  • 用时:20ms
  • 内存:92956kb
  • [2024-10-22 15:24:44]
  • 提交

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'