QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#385968 | #5440. P-P-Palindrome | wsc2008 | WA | 147ms | 66064kb | C++14 | 2.2kb | 2024-04-11 10:39:53 | 2024-04-11 10:39:54 |
Judging History
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=4e6+9,B=12379127;
ll m,n,len,R[N],tot,tid,ru;
ull pw[N],hsh[N];
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;
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;
}
}
}
ull H(ll l,ll r){
return (hsh[r]-hsh[l-1]*pw[r-l+1]);
}
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]);
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: 9ms
memory: 41964kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 7ms
memory: 42452kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 10ms
memory: 37204kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 7ms
memory: 42004kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 63ms
memory: 51204kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 67ms
memory: 51160kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: 0
Accepted
time: 147ms
memory: 66064kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133586
result:
ok 1 number(s): "133586"
Test #8:
score: 0
Accepted
time: 132ms
memory: 61320kb
input:
3 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...
output:
118967
result:
ok 1 number(s): "118967"
Test #9:
score: 0
Accepted
time: 123ms
memory: 60796kb
input:
3 bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...
output:
114444
result:
ok 1 number(s): "114444"
Test #10:
score: 0
Accepted
time: 138ms
memory: 60076kb
input:
3 abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...
output:
115321
result:
ok 1 number(s): "115321"
Test #11:
score: 0
Accepted
time: 143ms
memory: 62984kb
input:
3 azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...
output:
131825
result:
ok 1 number(s): "131825"
Test #12:
score: 0
Accepted
time: 12ms
memory: 44724kb
input:
3 yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...
output:
6
result:
ok 1 number(s): "6"
Test #13:
score: 0
Accepted
time: 15ms
memory: 47656kb
input:
3 azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...
output:
6
result:
ok 1 number(s): "6"
Test #14:
score: 0
Accepted
time: 9ms
memory: 46352kb
input:
3 byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...
output:
6
result:
ok 1 number(s): "6"
Test #15:
score: -100
Wrong Answer
time: 60ms
memory: 55380kb
input:
1 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...
output:
72248
result:
wrong answer 1st numbers differ - expected: '113382', found: '72248'