QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#278280 | #5065. Beautiful String | hhoppitree# | TL | 2698ms | 826192kb | C++14 | 1.8kb | 2023-12-07 14:33:58 | 2023-12-07 14:33:58 |
Judging History
answer
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=5010;
int lcp[N][N];
int F[N][N];
int T,n;
char s[N];
const __int128 P=1e18+9;
__int128 h[N],B=233;
gp_hash_table<long long,int>M;
int main()
{
cin>>T;
while(T--)
{
cin>>s+1;n=strlen(s+1);
memset(lcp,0,sizeof lcp);
memset(F,0,sizeof F);
for(int i=n;i;--i)
for(int j=n;j;--j)
lcp[i][j]=(lcp[i+1][j+1]+1)*(s[i]==s[j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=n&&j<=i&&j+i-1<=n;++j)
F[i][j]=lcp[i][i-j]>=j;
// for(int i=1;i<=n;++i)
// for(int j=1;j<=n;++j)
// cerr<<"F["<<i<<"]["<<j<<"]="<<F[i][j]<<endl;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
F[i][j]+=F[i][j-1];
for(int i=1;i<=n;++i)s[i]-='0';
long long ans=0;
for(int d=1;d<=n;++d)
{
int p=1;
__int128 up=0,b=1;
for(int i=1;i<=d;++i)b=b*B%P;
for(int i=1;i<d;++i)up=(up*B+s[i])%P;
for(int i=1,j=d;j<=n;++i,++j)
{
while(p<i-d)
{
M[h[p]]+=F[p][d-1];
// cerr<<"ADD: "<<p<<" "<<(long long)h[p]<<" "<<F[p][d-1]<<endl;
++p;
}
up=(up*B+s[j])%P;
if(i!=1)up=(up-b*s[i-1]%P+P)%P;
// cerr<<"RANGE: "<<i<<" "<<j<<" "<<(long long)up<<" "<<M[up]<<endl;
h[i]=up;
if(M.find(h[i])!=M.end())ans+=M[h[i]];
}
for(int i=1;i<p;++i)M[h[i]]-=F[i][d-1];
}
M.clear();
cout<<ans<<endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 31ms
memory: 199968kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: 0
Accepted
time: 2462ms
memory: 826192kb
input:
11 79380 2483905227 37902399703986576270 39991723655814713848046032694137883815354365954917 5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297 56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...
output:
0 0 0 2 4 20 119 113 1086 2128 15166
result:
ok 11 numbers
Test #3:
score: 0
Accepted
time: 851ms
memory: 200472kb
input:
50 11111111111111111111111111111111111111121111111111111111111111111111111111111112111111111121111111111211111121211121111111111111111111111111111211121111111111111111111111111111111111111111111111111112 111111111111111111111111111111111111111111111121111121111111111111111111111111111111111111111111...
output:
779344 799116 716078 723215 1197647 403357 652134 625671 414294 942493 390998 793444 612061 507395 473508 836065 461623 374925 539333 592574 676408 610940 463761 490048 995917 595830 424894 332669 596834 655095 521489 1032050 697420 752056 406316 360973 1180943 948628 478572 1026603 711224 429752 49...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 829ms
memory: 200876kb
input:
50 11211121122222111222111111222112111221112111121112221111111121211111212211212122112212221221112112221221112211211112121222112221211122112211112111112112211121222111222212211121111111112111112121111122 112112121211212111212221221222211211121212221111112122121211112221221121121112111221211112122121...
output:
7499 6375 7041 7889 6622 6804 8695 8795 7018 8387 8910 8019 8223 8820 7324 7144 8035 9941 7073 7373 7427 7280 6946 8204 7931 6769 7050 9268 7682 8232 7797 7356 7012 8967 7469 6869 11728 6562 7604 8840 7885 8658 7006 8156 10694 6716 6121 7499 7456 7981
result:
ok 50 numbers
Test #5:
score: 0
Accepted
time: 2698ms
memory: 297688kb
input:
15 111111111111111111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111...
output:
6611556286 8447635347 4351265656 8244172287 6847075843 5064323828 5818821992 5187397748 6202849391 7100699750 8826693258 9304467838 9691754783 12524687288 10378182916
result:
ok 15 numbers
Test #6:
score: -100
Time Limit Exceeded
input:
15 111111111111111111111111111111111111111111111111111111121112111111111111111111111111211111112111111111111111111111111112112111111111211111111111111111121211111111111111111112121111211112112111111112111111111111111112111111111111111111111111111111111111111211111211211111111111111112211111111111111...
output:
99283290 121730268 95231372 139100190 109487920 93015077 138212377 180336129 94959502 88117283 81796472 100172151 133716692 92198870