QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278432#5065. Beautiful Stringhhoppitree#TL 1801ms200628kbC++141.7kb2023-12-07 16:06:052023-12-07 16:06:05

Judging History

你现在查看的是最新测评结果

  • [2023-12-07 16:06:05]
  • 评测
  • 测评结果:TL
  • 用时:1801ms
  • 内存:200628kb
  • [2023-12-07 16:06:05]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize("Ofast")
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;M.clear();
            __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]];
            }
        }
        cout<<ans<<endl;
    }
}

详细

Test #1:

score: 100
Accepted
time: 16ms
memory: 199684kb

input:

2
114514
0000000

output:

1
3

result:

ok 2 number(s): "1 3"

Test #2:

score: 0
Accepted
time: 1075ms
memory: 200628kb

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: 767ms
memory: 199956kb

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: 794ms
memory: 199960kb

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: 1468ms
memory: 199848kb

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: 1801ms
memory: 199876kb

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: -100
Time Limit Exceeded

input:

6
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

385321895637
278064026340
462204013200
622961805899
319151572118

result: