QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#121708	#6408. Classical Counting Problem	SolitaryDream^#	AC ✓	1068ms	12612kb	C++20	1.6kb	2023-07-08 18:40:57	2023-07-08 18:41:01

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-07-08 18:41:01]
评测

测评结果：AC
用时：1068ms
内存：12612kb

查看

[2023-07-08 18:40:57]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int N=105;
const int Mod=998244353;
int a[N];
ll f[N][N*N];
ll res=0;
int n,m,v;
void calc(int s) {
    sort(a+1,a+n+1);
    int p=n;
    memset(f,0,sizeof(f));
    f[0][0]=1;
    DOR(i,n,1) {
        while(a[p]>a[i]+m) {
            FOR(j,0,n) FOR(k,0,n*101) {
                f[j][k]=f[j][k+101-a[p]];
                f[j+1][k+m]=(f[j+1][k+m]-f[j][k])%Mod;
                f[j][k+101-a[p]]=(f[j][k+101-a[p]]-f[j][k])%Mod;
            }
            DOR(j,n,0) DOR(k,n*101,0) {
                f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
                f[j][k]=0;
            }
            --p;
            // cerr << " --- " << endl;
        }
        // if(i==1) cerr << a[i] << endl;
        FOR(j,0,s-1) FOR(k,0,n*101) {
            if(k+m*i+(n-i-j)*(a[i]+m-101)>=m*v) {
                // if(i==2 && f[j][k]) cerr << j << ' ' << k << ' ' << f[j][k] << endl;
                res=(res+f[j][k])%Mod;
            }
        }
        DOR(j,n,0) DOR(k,n*101,0) {
            f[j+1][k+m]=(f[j+1][k+m]+f[j][k])%Mod;
            f[j][k+101-a[i]]=(f[j][k+101-a[i]]+f[j][k])%Mod;
            f[j][k]=0;
        }
    }
}
void solve() {
    cin >> n >> m >> v;
    FOR(i,1,n) cin >> a[i];
    res=1;
    calc(v);
    FOR(i,1,n) a[i]=100-a[i];
    v=n-v;
    calc(v-1);
    if(res<0) res+=Mod;
    cout << res << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 8ms

memory: 12448kb

input:

6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5

output:

result:

ok 6 numbers

Test #2:

score: 0

Accepted

time: 36ms

memory: 12468kb

input:

output:

result:

ok 50 numbers

Test #3:

score: 0

Accepted

time: 28ms

memory: 12400kb

input:

40
2 20 1
36 90
4 4 3
38 52 64 63
2 89 1
46 65
2 2 1
83 1
3 17 2
19 20 10
2 61 1
33 17
2 91 1
92 59
2 98 1
4 35
2 30 1
66 51
2 4 1
44 16
2 46 1
80 99
3 11 2
80 59 29
3 91 1
80 43 81
2 93 1
74 57
2 78 1
30 77
3 84 1
70 12 29
2 74 1
88 78
3 58 1
22 100 13
3 40 2
79 18 84
4 99 1
32 73 81 73
2 57 1
83 3...

output:

result:

ok 40 numbers

Test #4:

score: 0

Accepted

time: 24ms

memory: 12612kb

input:

30
3 82 1
18 19 77
4 22 1
63 42 11 42
2 60 1
25 90
3 87 2
21 47 5
2 50 1
88 81
4 71 1
63 29 19 68
6 69 3
13 4 71 96 73 39
3 83 2
29 88 28
2 56 1
84 20
2 43 1
8 29
2 48 1
43 9
3 88 1
12 88 58
6 42 4
16 33 47 70 66 42
7 71 1
95 96 18 92 9 20 4
3 11 1
64 46 83
2 7 1
72 49
2 35 1
15 24
3 50 2
82 22 48
4...

output:

result:

ok 30 numbers

Test #5:

score: 0

Accepted

time: 21ms

memory: 12472kb

input:

20
7 41 6
9 17 92 61 58 10 96
2 97 1
84 29
2 83 1
52 65
4 28 3
28 81 53 74
9 69 5
10 80 90 1 91 21 81 96 60
3 66 1
21 9 24
7 88 6
34 21 5 100 51 68 88
2 49 1
62 7
2 6 1
10 1
6 21 1
54 0 16 8 61 16
3 22 2
10 13 75
5 20 1
77 4 16 16 38
5 26 4
31 14 85 69 20
3 31 2
36 58 78
11 39 6
47 7 79 15 34 99 29 ...

output:

result:

ok 20 numbers

Test #6:

score: 0

Accepted

time: 101ms

memory: 12472kb

input:

10
6 32 4
3 64 60 50 71 92
5 17 3
34 22 90 94 35
46 34 44
33 32 55 85 54 4 8 56 87 90 86 88 6 76 12 76 31 80 58 70 99 92 13 59 82 20 25 97 29 64 16 39 57 40 19 17 48 86 6 60 89 99 71 83 95 6
3 62 1
60 0 96
11 85 7
79 92 34 24 79 36 75 89 78 60 5
3 91 2
55 18 29
12 41 5
75 4 81 73 71 93 50 10 43 55 6...

output:

result:

ok 10 numbers

Test #7:

score: 0

Accepted

time: 95ms

memory: 12424kb

input:

5
40 23 31
75 10 19 30 90 96 40 84 96 20 44 61 24 46 39 56 1 73 54 83 85 3 13 14 45 46 39 99 91 99 48 89 28 75 62 5 24 51 61 11
16 62 2
96 5 95 8 67 28 36 20 20 48 89 64 11 50 56 38
15 53 7
43 10 69 97 98 99 38 88 78 74 57 69 0 78 61
27 67 6
74 37 76 8 74 42 76 6 68 94 49 55 10 28 35 25 17 41 65 85 ...

output:

result:

ok 5 number(s): "26111 2098 2839 2739716 3"

Test #8:

score: 0

Accepted

time: 77ms

memory: 12472kb

input:

4
17 100 14
65 87 80 62 80 85 47 14 13 23 91 39 5 82 59 28 46
14 83 8
46 14 88 24 70 57 14 6 63 18 98 68 20 10
40 94 16
91 33 82 64 50 16 2 64 39 76 75 35 20 0 53 14 74 2 44 83 51 67 97 93 61 77 56 12 29 95 77 7 78 46 85 76 76 38 22 94
29 3 5
27 14 12 21 45 42 2 41 92 27 54 46 15 73 38 99 68 96 79 1...

output:

result:

ok 4 number(s): "40145 8703 880766959 64"

Test #9:

score: 0

Accepted

time: 219ms

memory: 12556kb

input:

3
64 81 26
6 35 9 39 70 29 91 9 54 21 83 73 10 93 96 40 50 92 88 87 71 70 22 45 4 23 18 10 88 71 73 5 49 67 12 28 8 61 73 19 27 89 64 65 94 93 87 61 40 4 37 66 72 100 54 33 80 40 26 46 85 59 1 50
26 6 12
56 37 5 5 3 67 52 53 77 55 39 89 86 55 78 34 83 78 75 51 9 43 2 18 86 14
10 89 1
10 41 16 63 14 ...

output:

923730397
139
230

result:

ok 3 number(s): "923730397 139 230"

Test #10:

score: 0

Accepted

time: 276ms

memory: 12468kb

input:

2
56 3 30
67 80 38 54 30 78 45 29 61 28 97 77 43 38 37 75 54 84 81 32 16 63 2 90 34 95 54 88 2 44 23 37 87 20 78 71 66 4 21 52 99 15 94 4 66 37 41 100 88 26 76 10 16 36 32 63
44 49 2
24 0 0 33 9 3 41 39 91 46 13 12 43 11 68 28 0 31 16 73 21 22 72 53 79 65 92 80 26 62 93 97 48 90 77 11 4 54 19 21 89 ...

output:

267
343867

result:

ok 2 number(s): "267 343867"

Test #11:

score: 0

Accepted

time: 537ms

memory: 12468kb

input:

1
100 97 9
57 74 56 14 12 8 50 94 81 32 50 70 75 66 44 40 51 71 90 59 66 8 81 31 36 7 81 44 53 85 43 45 49 37 63 56 71 20 81 83 71 51 3 78 47 28 13 41 50 32 23 82 52 32 1 83 63 7 97 78 6 71 88 2 98 14 29 83 74 71 81 96 89 30 48 5 64 74 63 74 96 12 2 36 26 75 7 44 66 93 82 31 13 86 5 96 8 10 71 70

output:

421427517

result:

ok 1 number(s): "421427517"

Test #12:

score: 0

Accepted

time: 1052ms

memory: 12400kb

input:

1
100 21 58
67 6 11 89 1 59 8 18 80 33 58 27 5 65 73 17 35 15 31 81 18 12 56 9 49 72 74 74 98 25 68 96 10 75 22 48 43 50 9 38 13 38 82 21 37 66 21 86 83 89 0 73 84 39 77 30 66 26 25 89 14 22 71 75 51 70 41 43 12 70 4 25 20 71 62 1 47 79 66 87 87 95 74 63 97 21 83 28 52 90 90 44 34 55 67 69 90 20 62 66

output:

879050745

result:

ok 1 number(s): "879050745"

Test #13:

score: 0

Accepted

time: 862ms

memory: 12436kb

input:

1
100 49 5
41 64 55 30 13 20 100 9 12 45 33 28 25 64 81 71 19 36 83 14 72 16 99 44 95 12 23 3 18 89 49 80 15 23 59 7 16 79 13 61 67 57 60 31 94 3 86 54 80 0 99 74 47 80 64 78 23 56 64 78 55 85 75 59 61 57 53 38 72 70 61 76 7 77 52 30 41 28 1 55 9 77 33 79 56 67 92 46 6 20 29 13 88 47 5 9 83 86 75 19

output:

778551245

result:

ok 1 number(s): "778551245"

Test #14:

score: 0

Accepted

time: 802ms

memory: 12480kb

input:

1
100 73 50
62 54 10 15 91 71 92 68 12 56 77 86 56 74 77 82 71 91 57 48 24 88 41 90 40 8 50 33 96 97 74 30 77 28 52 100 90 98 75 6 53 44 26 75 84 74 94 99 45 80 42 75 10 87 75 93 59 18 24 21 31 47 46 31 70 34 76 33 10 36 51 60 95 51 99 25 25 78 14 57 100 92 72 95 25 81 0 97 94 50 80 48 8 38 77 39 97...

output:

966167597

result:

ok 1 number(s): "966167597"

Test #15:

score: 0

Accepted

time: 536ms

memory: 12448kb

input:

1
100 97 8
72 76 65 90 46 54 39 59 11 35 74 88 76 73 6 35 55 68 99 71 66 93 16 69 54 73 100 31 74 26 66 81 37 9 44 24 95 60 47 29 6 41 4 96 40 44 69 66 78 70 40 99 74 94 51 73 51 37 64 10 72 42 17 71 23 22 88 39 71 24 7 11 83 24 78 21 8 16 50 92 23 74 43 89 85 59 87 3 81 48 87 50 29 7 37 13 21 93 90...

output:

578242220

result:

ok 1 number(s): "578242220"

Test #16:

score: 0

Accepted

time: 1068ms

memory: 12428kb

input:

1
100 21 50
24 66 9 30 59 72 31 84 0 36 49 78 96 72 13 45 7 23 39 36 87 75 92 36 100 13 93 61 62 68 47 32 31 48 37 95 35 89 8 86 82 61 83 39 30 49 77 78 76 49 84 67 4 34 27 20 76 0 92 21 80 71 32 22 33 9 10 67 9 24 53 74 13 98 57 50 35 33 52 59 13 23 3 37 44 5 63 20 35 89 27 19 39 31 8 87 2 91 3 44

output:

474759161

result:

ok 1 number(s): "474759161"

Test #17:

score: 0

Accepted

time: 870ms

memory: 12440kb

input:

1
100 49 99
34 100 64 15 47 22 90 75 100 47 25 79 26 3 43 99 2 68 24 70 39 79 34 82 45 10 87 80 6 98 4 15 3 64 63 87 97 40 80 30 35 47 49 17 54 19 85 79 29 60 61 90 24 30 70 67 44 63 30 43 20 66 3 95 43 98 22 62 81 91 9 57 0 3 71 46 18 83 99 72 36 48 42 20 14 18 39 38 22 87 67 21 60 0 70 95 84 0 95 40

output:

result:

ok 1 number(s): "3181458"

Test #18:

score: 0

Accepted

time: 749ms

memory: 12612kb

input:

1
100 73 46
54 89 87 57 92 73 49 33 32 59 33 36 46 2 50 8 87 56 65 60 13 50 77 28 58 40 69 10 95 39 97 66 65 34 56 46 2 70 52 54 89 67 27 60 77 90 49 90 95 6 59 59 88 70 46 14 69 82 58 55 61 17 76 67 53 86 34 57 8 22 99 8 89 45 62 75 1 21 33 6 16 30 13 47 74 98 47 56 88 49 85 56 49 60 41 69 76 66 86...

output:

353900212

result:

ok 1 number(s): "353900212"

Test #19:

score: 0

Accepted

time: 547ms

memory: 12396kb

input:

1
100 98 91
64 11 31 31 37 23 40 57 32 38 8 38 77 12 47 30 38 10 39 94 67 54 63 74 36 15 62 7 72 69 22 50 58 50 48 38 75 99 46 99 64 86 27 71 0 95 57 91 60 29 2 82 51 78 33 95 61 11 63 66 36 80 80 51 6 40 24 52 79 90 22 60 8 51 41 3 96 71 69 75 6 45 74 63 0 11 23 73 75 47 24 25 70 95 12 42 57 42 99 45

output:

991832540

result:

ok 1 number(s): "991832540"

Test #20:

score: 0

Accepted

time: 801ms

memory: 12440kb

input:

1
100 64 65
80 91 56 8 83 44 39 75 86 39 83 29 32 56 6 44 84 43 6 19 97 94 20 48 69 59 15 79 30 89 98 63 87 95 49 50 53 19 70 16 47 93 78 67 100 59 51 81 82 61 5 62 96 89 33 40 38 19 78 8 7 38 77 55 31 78 27 3 53 20 63 95 38 93 72 12 41 59 38 96 68 47 17 81 14 56 54 83 40 75 9 7 96 55 77 51 48 25 1 78

output:

267899508

result:

ok 1 number(s): "267899508"

Test #21:

score: 0

Accepted

time: 500ms

memory: 12420kb

input:

1
100 100 99
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

436278057

result:

ok 1 number(s): "436278057"

Test #22:

score: 0

Accepted

time: 919ms

memory: 12472kb

input:

1
100 1 99
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 1...

output:

131961966

result:

ok 1 number(s): "131961966"

Test #23:

score: 0

Accepted

time: 504ms

memory: 12436kb

input:

1
100 100 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

436278057

result:

ok 1 number(s): "436278057"

Test #24:

score: 0

Accepted

time: 921ms

memory: 12452kb

input:

1
100 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 10...

output:

131961966

result:

ok 1 number(s): "131961966"

Test #25:

score: 0

Accepted

time: 531ms

memory: 12400kb

input:

1
100 100 99
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #26:

score: 0

Accepted

time: 665ms

memory: 12612kb

input:

1
100 1 99
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 1...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #27:

score: 0

Accepted

time: 533ms

memory: 12544kb

input:

1
100 100 1
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...

output:

882499717

result:

ok 1 number(s): "882499717"

Test #28:

score: 0

Accepted

time: 624ms

memory: 12396kb

input:

1
100 1 1
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 10...

output:

882499717

result:

ok 1 number(s): "882499717"