QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#278506#5065. Beautiful Stringhhoppitree#WA 2820ms102076kbC++141.8kb2023-12-07 16:47:052023-12-07 16:47:05

Judging History

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

  • [2023-12-07 16:47:05]
  • 评测
  • 测评结果:WA
  • 用时:2820ms
  • 内存:102076kb
  • [2023-12-07 16:47:05]
  • 提交

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'