QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#706711 | #6567. Repetitive String Invention | ucup-team902# | WA | 1077ms | 614448kb | C++17 | 1.1kb | 2024-11-03 13:04:59 | 2024-11-03 13:05:01 |
Judging History
answer
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll=long long;
const int N=800;
const int g=27,mod=998244353;
int n;
char s[N+5];
int hv[N+5][N+5];
gp_hash_table<int,int> cnt[N+5],cnt2[N+5];
ll ans;
int main(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
for(int j=i;j<=n&&j-i+1<=n/2;j++){
hv[i][j]=(1ll*hv[i][j-1]*g+s[j]-'a'+1)%mod;
for(int k=1;k<=i;k++)
cnt[k][hv[i][j]]++;
for(int k=j;k<=n;k++)
cnt2[k][hv[i][j]]++;
}
for(int d=1;d<=n/2;d++){
for(int i=1;i<=n;i++){
for(int j=i+d-1;j<=n&&j-i+1<2*d;j++){
if(hv[i][j-d]==hv[i+d][j])
ans+=cnt[j+1][hv[j-d+1][i+d-1]];
}
}
for(int i=1;i<=n;i++)
for(int j=i+d;j<=n&&j-i+1<2*d;j++){
if(hv[i][j-d]==hv[i+d][j])
ans+=cnt2[i-1][hv[j-d+1][i+d-1]];
}
}
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 6288kb
input:
aaaa
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4296kb
input:
axabxbcxcdxd
output:
22
result:
ok single line: '22'
Test #3:
score: 0
Accepted
time: 112ms
memory: 9812kb
input:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
536006700
result:
ok single line: '536006700'
Test #4:
score: 0
Accepted
time: 122ms
memory: 14412kb
input:
abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...
output:
136016600
result:
ok single line: '136016600'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4464kb
input:
a
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4436kb
input:
ab
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4236kb
input:
aa
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 874ms
memory: 560540kb
input:
bbbbbrrrrbrbrrbrbrbrbbrrbbbbrrbrrbrbrbrrrrrbbbrrbrrbbrrrbbbbbrrrrbbrbbrrrrrbbrrrbbbbbrbbrbbbrbrrbrrrrrrrrbbrbrbbrrrrrrbbbbbrbrrrrbrrbbrbrrrrrbrbrbbrbrrbrrrrbrbbrbrrbrrbbbbrrrrrbrbbrbbrrrrrbrbrbrbbbrrrrrrrbbbbbbrrbrbrrrrrbbbrbrrrrbbbbrrbrrbbbbbbbrbbbbrrrbrbbbrrrrrrbbbbbrbrrbbbbrbrbrrbbrrrbbbrbbbrbbrr...
output:
209015
result:
ok single line: '209015'
Test #9:
score: 0
Accepted
time: 961ms
memory: 587004kb
input:
fkrryithikkpurfezufbthxxrtejxpprhrhurrfziigzgajipayrefarpxuggehkiggeppfjghuyejuagkjpiezhmfizgphkkfffifihrimuhgtgzykfupbprjyrbpbimapjmbkrhubzhgfhhpkrxgjgmkheiiugiyerggyukyfuuxgrehgayafzuxymxxabygpapbjxipkxgbxhzpekypfghaumukguaipphiyhzimzfmpmzahbmaagytygyekzhktbbheetxrbipgytppgbhkpimrybkbeirhrzytfehba...
output:
5696
result:
ok single line: '5696'
Test #10:
score: 0
Accepted
time: 1077ms
memory: 614448kb
input:
ayeaecauuueerrcsyyyuayauarecyrruueeucacrrcesercyeasuscucscruaaresaeruurreeursssuyraeysurecacueuacycacsyuyeyusssassaasyuarrcecueayacucuyyrsasrycyrrcececyuccecyreyeccuesaasceasussaraeruyarcauarcecacrucryryseysauaucyaeyurueurerrccrayyyycccsuaaesrecurucerrascyacucucryarycayeesyysusserarseyrauyrryeacauec...
output:
18249
result:
ok single line: '18249'
Test #11:
score: 0
Accepted
time: 897ms
memory: 546964kb
input:
lclccclcclllccccclcclclcccclllllcclcclclcclllllcllccclclclccclccllcclccccccllccclclcccclclcclclccclllllccclcccccclllllccllcclclllllllccclllcllllccccccccllccclllccclcllllllllcclccclccccllccllclclcclcllcllccclcllclllclclllclllcllcclclllccclcclclllclllllllcclllcccccllcllcllcclcclcllccclclllclclcccllcll...
output:
207835
result:
ok single line: '207835'
Test #12:
score: -100
Wrong Answer
time: 1007ms
memory: 613792kb
input:
lygxvkxeeiixzzpamosqadacrnyierrztikxheupgbkfkstyjrmyvhmjrhfhwfdeyhzuyhhbczbjgcnzouiufetegmnvxoeqxiykkwysdnnmdjtpwwzpdaqzmwmapbqbdjsdoxmpbvseyfrrqpgteehoxqsjszykfqgdmcgwikavcnhoubonianpecjtumdutpxwioqtkystzndrbtlfircdsnsxraoitswvhjirqxxjrnjjsldbmdcjngecdaotrgxvikyfyjlbbeketxrxeknuxmxehvabyyyxnrchukft...
output:
3444
result:
wrong answer 1st lines differ - expected: '3442', found: '3444'