QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#385960#5440. P-P-Palindromewsc2008WA 147ms57352kbC++142.2kb2024-04-11 10:36:582024-04-11 10:36:59

Judging History

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

  • [2024-04-11 10:36:59]
  • 评测
  • 测评结果:WA
  • 用时:147ms
  • 内存:57352kb
  • [2024-04-11 10:36:58]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
//对于两个回文串 P, Q, P+Q 是回文串当且仅当 P 和 Q 的最小循环节相同
//对于每个 s_i,求出所有本质不同回文串和最小循环节,用哈希判断
const ll N=2e6+9,Mod=998244353,B=184737;
ll m,n,len,pw[N],hsh[N],R[N],tot,tid,ru;
ll pr[N],prc,minp[N],vis[N];
char s[N],t[N];
void init(ll n){
	pw[0]=1;
	rep(i,1,n)pw[i]=pw[i-1]*B%Mod;
	minp[1]=1;
	rep(i,2,n){
		if(!vis[i])pr[++prc]=i,minp[i]=i;
		rep(j,1,prc){
			if(pr[j]*i>n)break;
			vis[i*pr[j]]=1;
			minp[i*pr[j]]=pr[j];
			if(i%pr[j]==0)break;
		}
	}
}
ll H(ll l,ll r){
	return (hsh[r]-hsh[l-1]*pw[r-l+1]%Mod+Mod)%Mod;
}
ll Bord(ll l,ll r){//查询 [l,r] 循环节
	if(H(l+1,r)==H(l,r-1))return 1;
	ll len=r-l+1,res=r-l+1;
	while(len>1){
		if(H(l+res/minp[len],r)==H(l,r-res/minp[len]))res/=minp[len];
		len/=minp[len];
	}
	return res;
}
struct Seg{
	ll l,r;
}str[N];
map<ll,ll>mp1,mp2;
bool Med;
int main(){
	cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
	m=read();
	init(1e6);
	while(m--){
		scanf("%s",s+1);
		n=strlen(s+1);
		rep(i,1,n)hsh[i]=(hsh[i-1]*B+s[i])%Mod;
		len=0;
		t[++len]='$';
		rep(i,1,n)t[++len]='#',t[++len]=s[i];
		t[++len]='#',t[++len]='*';
		rep(i,0,len)R[i]=0;
		ll mx=0,id=0;
		tot=0;
		rep(i,1,len){
			if(i<=mx)R[i]=min(R[2*id-i],mx-i+1);
			while(t[i-R[i]]==t[i+R[i]]){
				if(isalpha(t[i-R[i]]))tot++,str[tot]=(Seg){(i-R[i])/2,(i+R[i])/2};
				R[i]++;
			}
			if(i+R[i]-1>mx)mx=i+R[i]-1,id=i;
		}
		rep(i,1,tot){
			ll hs=H(str[i].l,str[i].r);
			if(mp1.find(hs)!=mp1.end())continue;
			mp1[hs]=1;
			ll o=Bord(str[i].l,str[i].r);
			hs=H(str[i].l,str[i].l+o-1);
			mp2[hs]++;
		}
	}
	ll ans=0;
	for(pii p:mp2)ans+=p.second*p.second;
	write(ans);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 13ms
memory: 39088kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 0ms
memory: 37488kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 11ms
memory: 41392kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: 0
Accepted
time: 8ms
memory: 41980kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1282

result:

ok 1 number(s): "1282"

Test #5:

score: 0
Accepted
time: 72ms
memory: 47736kb

input:

5
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #6:

score: 0
Accepted
time: 80ms
memory: 47128kb

input:

5
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

3600000000

result:

ok 1 number(s): "3600000000"

Test #7:

score: -100
Wrong Answer
time: 147ms
memory: 57352kb

input:

3
abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...

output:

133577

result:

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