QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#151588#5440. P-P-PalindromeTadijaSebezWA 7ms12512kbC++141.9kb2023-08-27 04:27:362023-08-27 04:27:40

Judging History

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

  • [2023-08-27 04:27:40]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:12512kb
  • [2023-08-27 04:27:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}

const int N=1000050;
const int base=37;
int po[N];

char s[N];

int img,zero,tsz,go[N][26],link[N],len[N];
int hsh[N];

void init(){
	img=++tsz;
	zero=++tsz;
	len[img]=-1;
	len[zero]=0;
	link[zero]=img;
	link[img]=img;

	po[0]=1;
	for(int i=1;i<N;i++){
		po[i]=mul(po[i-1],base);
	}
}

set<pair<int,int>> all;
void DFS(int u){
	if(len[u]>0){
		all.insert({len[u],hsh[u]});
	}
	for(int i=0;i<26;i++){
		if(go[u][i]){
			hsh[go[u][i]]=add(add(i+1,mul(i+1,po[len[u]+1])),mul(hsh[u],base));
			DFS(go[u][i]);
		}
	}
}
int main(){
	int n;
	scanf("%i",&n);
	init();
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		int m=strlen(s+1);
		int curr=zero;
		for(int j=1;j<=m;j++){
			while(j-len[curr]-1<=0 || s[j]!=s[j-len[curr]-1]){
				curr=link[curr];
			}
			int next=go[curr][s[j]-'a'];
			if(next==0){
				next=++tsz;
				go[curr][s[j]-'a']=next;
				len[next]=len[curr]+2;
				int up=link[curr];
				while(up!=img && go[up][s[j]-'a']==0){
					up=link[up];
				}
				if(go[up][s[j]-'a']!=0 && len[next]!=1){
					link[next]=go[up][s[j]-'a'];
				}else{
					link[next]=zero;
				}
			}
			curr=next;
		}
	}
	hsh[zero]=0;
	DFS(zero);
	for(int i=0;i<26;i++){
		if(go[img][i]!=0){
			hsh[go[img][i]]=i+1;
			DFS(go[img][i]);
		}
	}
	ll ans=0;
	while(all.size()){
		int len=all.begin()->first;
		int hsh=all.begin()->second;
		int len1=len;
		int hsh1=hsh;
		int cnt=0;
		while(true){
			if(all.count({len1,hsh1})){
				cnt++;
				all.erase({len1,hsh1});
				len1+=len;
				hsh1=add(hsh,mul(po[len],hsh1));
			}else{
				break;
			}
		}
		ans+=(ll)cnt*cnt;
	}
	printf("%lld\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 12292kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 7ms
memory: 12428kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 1ms
memory: 11840kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 12512kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1272

result:

wrong answer 1st numbers differ - expected: '1282', found: '1272'