QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#278506 | #5065. Beautiful String | hhoppitree# | WA | 2820ms | 102076kb | C++14 | 1.8kb | 2023-12-07 16:47:05 | 2023-12-07 16:47:05 |
Judging History
answer
#pragma optimize("Ofast")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
const int N=5010;
short lcp[N][N];
short F[N][N];
int T,n;
char s[N];
const int P=1e9+7,B=233;
long long h[N];
gp_hash_table<int,int>M;
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--)
{
cin>>s+1;n=strlen(s+1);
for(int i=1;i<=n+1;++i)
memset(lcp[i],0,sizeof(short)*(n+5)),
memset(F[i],0,sizeof(short)*(n+5));
for(int i=n;i;--i)
for(int j=1;j<=n;++j)
(s[i]==s[j]?(lcp[i][j]=lcp[i+1][j+1]+1):0);
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 j=1;j<=n;++j)
F[i][j]+=F[i][j-1];
}
// 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)s[i]-='0';
long long ans=0,b=P-1;
for(int d=1;d<=n;++d)
{
int p=1;M.clear();
long long up=0;
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;
// cerr<<"RANGE: "<<i<<" "<<j<<" "<<(long long)up<<" "<<M[up]<<endl;
h[i]=up;
if(M.find(h[i])!=M.end())
ans+=M[h[i]];
}
}
cout<<ans<<endl;
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: 0
Accepted
time: 594ms
memory: 101772kb
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: 28ms
memory: 9996kb
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: 37ms
memory: 10360kb
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: 860ms
memory: 43700kb
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: 0
Accepted
time: 1054ms
memory: 47080kb
input:
15 111111111111111111111111111111111111111111111111111111121112111111111111111111111111211111112111111111111111111111111112112111111111211111111111111111121211111111111111111112121111211112112111111112111111111111111112111111111111111111111111111111111111111211111211211111111111111112211111111111111...
output:
99283290 121730268 95231372 139100190 109487920 93015077 138212377 180336129 94959502 88117283 81796472 100172151 133716692 92198870 119549081
result:
ok 15 numbers
Test #7:
score: 0
Accepted
time: 2119ms
memory: 101844kb
input:
6 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
385321895637 278064026340 462204013200 622961805899 319151572118 194136546751
result:
ok 6 numbers
Test #8:
score: 0
Accepted
time: 2679ms
memory: 102076kb
input:
6 1111211111111111111111111112111111111111111111111111111111111111111111111111111111111111111121111111112111111111111111111111211111111111111111111111111111111111111111111111111111112111111111111111111111111111111111111111111111111111111111111111111111111111111211111111112111111111111111111111111111...
output:
4279296283 6481388714 4807510535 5043682133 5816318027 4092854445
result:
ok 6 numbers
Test #9:
score: 0
Accepted
time: 1356ms
memory: 101648kb
input:
6 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4333336111111 4333336111111 4333336111111 4333336111111 4333336111111 4333336111111
result:
ok 6 numbers
Test #10:
score: 0
Accepted
time: 2688ms
memory: 101848kb
input:
6 1111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
4827246439 5292779668 4777240971 4935748521 5102858676 4471955490
result:
ok 6 numbers
Test #11:
score: 0
Accepted
time: 2694ms
memory: 102040kb
input:
6 1111111111112111111112111111111111111211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111112111111111111111111111111111111111111111111111121111111111111111111111111111111111111111111111111111111121111111111111111111111111...
output:
5823633843 3699828594 5341000227 4377298465 5641079075 4447500985
result:
ok 6 numbers
Test #12:
score: 0
Accepted
time: 2689ms
memory: 101724kb
input:
6 1111111111111111111111111111111121121111111111111111112111111111111111111111111111111111111111111111111211111111111111111111121111111111111111111111111111111111111111111111111111111121111111111211111111111111111111111111121111112111111111111111111111111111111111111111111111111112111111111111111111...
output:
4267388536 4492067906 3738167207 4136464174 5508219259 4485317348
result:
ok 6 numbers
Test #13:
score: -100
Wrong Answer
time: 2820ms
memory: 101872kb
input:
6 1101000101000011111101010011000111011101101000100101001011110000000010100000011011010010110000100000100100101110000010110010101011011100101000111010101110101010100011011111111111101001110101011000000011100011110001100001100101101111101011101110001000100110011001101100000010111111000010010110100011...
output:
4170757 4235315 4280843 4036741 4224797 4097582
result:
wrong answer 2nd numbers differ - expected: '4235303', found: '4235315'