QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108771 | #5440. P-P-Palindrome | zhanghaojie | WA | 185ms | 37064kb | C++14 | 1.4kb | 2023-05-26 17:11:54 | 2023-05-26 17:12:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,P = 13331;
typedef long long LL;
typedef unsigned long long ULL;
struct Node
{
int ch[26];
int len,fail;
}tr[N];
char s[N];
int n,cnt,tot,las;
ULL p[N],h[N];
map<ULL,int> mp;
LL ans;
int new_node(int l)
{
int p=++tot;
memset(tr[p].ch,0,sizeof tr[p].ch);
tr[p].fail=0;
tr[p].len=l;
return p;
}
void init()
{
cnt=las=0;
tot=-1;
new_node(0);
new_node(-1);
tr[0].fail=1;
}
int find_fail(int x)
{
while(s[cnt]!=s[cnt-tr[x].len-1]) x=tr[x].fail;
return x;
}
void insert(int x)
{
int now=find_fail(las);
if(!tr[now].ch[x])
{
int p=new_node(tr[now].len+2);
tr[p].fail=tr[find_fail(tr[now].fail)].ch[x];
tr[now].ch[x]=p;
}
las=tr[now].ch[x];
}
ULL sr(int l,int r)
{
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
p[0]=1;
for(int i=1;i<N;i++)
p[i]=p[i-1]*P;
int t;
cin>>t;
while(t--)
{
scanf("%s",s+1);
n=strlen(s+1);
init();
for(int i=1;i<=n;i++)
h[i]=h[i-1]*P+s[i];
for(int i=1;i<=n;i++)
{
cnt++;
insert(s[i]-'a');
int len=tr[las].len,flen=tr[tr[las].fail].len;
int diff=len-flen;
if(len%diff!=0)
diff=len;
ULL tmp=sr(i-diff+1,i);
if(!mp[tmp]) mp[tmp]=len/diff;
else mp[tmp]=max(mp[tmp],len/diff);
}
}
for(auto i:mp)
ans+=1ll*i.second*i.second;
cout<<ans<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 13752kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 1ms
memory: 15716kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 1ms
memory: 13664kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: 0
Accepted
time: 7ms
memory: 15664kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1282
result:
ok 1 number(s): "1282"
Test #5:
score: 0
Accepted
time: 14ms
memory: 22340kb
input:
5 ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #6:
score: 0
Accepted
time: 18ms
memory: 20328kb
input:
5 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...
output:
3600000000
result:
ok 1 number(s): "3600000000"
Test #7:
score: 0
Accepted
time: 161ms
memory: 35076kb
input:
3 abbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbab...
output:
133586
result:
ok 1 number(s): "133586"
Test #8:
score: 0
Accepted
time: 153ms
memory: 35684kb
input:
3 abbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbabab...
output:
118967
result:
ok 1 number(s): "118967"
Test #9:
score: 0
Accepted
time: 129ms
memory: 35292kb
input:
3 bbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabb...
output:
114444
result:
ok 1 number(s): "114444"
Test #10:
score: 0
Accepted
time: 185ms
memory: 31828kb
input:
3 abbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbababbababbabbababbababbabbababbabbababbababbabbababbabbabab...
output:
115321
result:
ok 1 number(s): "115321"
Test #11:
score: 0
Accepted
time: 158ms
memory: 37064kb
input:
3 azzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazzazazzazazzazzazazzazazzazzazazzazzazazzazazzazzazaz...
output:
131825
result:
ok 1 number(s): "131825"
Test #12:
score: 0
Accepted
time: 15ms
memory: 16196kb
input:
3 yazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbyb...
output:
6
result:
ok 1 number(s): "6"
Test #13:
score: 0
Accepted
time: 9ms
memory: 16496kb
input:
3 azbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazby...
output:
6
result:
ok 1 number(s): "6"
Test #14:
score: 0
Accepted
time: 10ms
memory: 16156kb
input:
3 byazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbyazbybyazbybyazbyazbybyazbybyazbyazbybyaz...
output:
6
result:
ok 1 number(s): "6"
Test #15:
score: -100
Wrong Answer
time: 56ms
memory: 33036kb
input:
1 abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabba...
output:
70307
result:
wrong answer 1st numbers differ - expected: '113382', found: '70307'