QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#169000#6408. Classical Counting ProblemrealIyxiangAC ✓34ms7976kbC++141.7kb2023-09-09 10:32:012023-09-09 10:32:02

Judging History

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

  • [2023-09-09 10:32:02]
  • 评测
  • 测评结果:AC
  • 用时:34ms
  • 内存:7976kb
  • [2023-09-09 10:32:01]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 1e2 + 5;
const int P = 998244353; 
int n, m, v, q, T, ans, a[N], f[N][N * N]; 

int inc (int a, int b) { return (a += b) >= P ? a - P : a; }
int dec (int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul (int a, int b) { return 1ll * a * b % P; }
int fpow (int a, int b) { int ans = 1; for ( ; b; a = mul(a, a), b >>= 1) if(b & 1) ans = mul(ans, a); return ans; }

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); 
  cin >> T;
  while (T--) {
    cin >> n >> m >> v, ans = 0;
    rep(i, 1, n) cin >> a[i]; 
    sort(a + 1, a + n + 1, [](int a, int b) { return a > b; }); 
    rep(y, 1, n) {
      rep(i, 1, y - 1) rep(j, 0, m * (y - 1)) f[i][j] = 0; 
      f[0][0] = 1; 
      rep(i, 1, y - 1) rep(j, 0, i * m) {
        if(j >= m) f[i][j] = inc(f[i][j], f[i - 1][j - m]); 
        if(a[i] - a[y] <= m) {
          q = (a[y] + m - a[i]); 
          if(q <= j) f[i][j] = inc(f[i][j], f[i - 1][j - q]); 
        }
      }
      rep(i, 0, (y - 1) * m) if(i + (n - y + 1) * m >= m * v) 
        ans = inc(ans, f[y - 1][i]); 
    }
    rep(x, 1, n) {
      rep(i, x, n) rep(j, 0, m * (n - x)) f[i][j] = 0; 
      f[x][0] = 1; 
      rep(i, x + 1, n) rep(j, 0, m * (i - x)) {
        f[i][j] = f[i - 1][j]; 
        if(a[x] - a[i] <= m) {
          q = a[x] - a[i]; 
          if(q <= j) f[i][j] = inc(f[i][j], f[i - 1][j - q]); 
        }
      }
      rep(i, 0, m * (n - x)) if(i > m * v) ans = dec(ans, f[n][i]); 
    }
    cout << ans << '\n'; 
  }
  return 0; 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3684kb

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:

5
6
1023
23
19
240

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

50
2 62 1
67 58
2 23 1
7 39
2 60 1
53 9
2 29 1
3 68
2 52 1
43 76
2 79 1
48 91
2 85 1
18 11
2 34 1
19 24
2 42 1
77 44
2 54 1
80 49
2 90 1
61 55
2 24 1
51 72
2 8 1
9 8
2 83 1
91 0
2 33 1
27 27
2 30 1
8 99
2 52 1
34 87
2 51 1
13 47
2 16 1
0 27
2 63 1
53 76
2 25 1
82 36
2 42 1
53 54
2 12 1
38 70
2 2 1
6...

output:

3
2
3
2
3
3
3
3
3
3
3
3
3
2
3
2
2
3
2
3
2
3
2
2
2
3
3
2
3
3
3
2
2
2
3
3
3
2
3
2
3
3
3
3
3
3
3
3
3
3

result:

ok 50 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3612kb

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:

2
5
3
2
6
3
3
3
3
2
3
3
7
3
3
6
3
4
4
15
3
7
2
4
5
2
3
3
2
2
7
3
2
3
3
15
3
3
2
7

result:

ok 40 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 5716kb

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:

6
7
2
7
3
12
39
7
2
3
3
6
38
22
3
2
3
5
6
7
7
3
18
2
55
3
4
3
7
7

result:

ok 30 numbers

Test #5:

score: 0
Accepted
time: 1ms
memory: 3732kb

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:

20
3
3
8
91
7
43
2
2
15
4
9
10
5
117
3
82
15
545
7

result:

ok 20 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 4192kb

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:

24
10
85407
5
1426
7
647
2
6
19

result:

ok 10 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 3988kb

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:

26111
2098
2839
2739716
3

result:

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

Test #8:

score: 0
Accepted
time: 1ms
memory: 6228kb

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:

40145
8703
880766959
64

result:

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

Test #9:

score: 0
Accepted
time: 8ms
memory: 6796kb

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: 2ms
memory: 6144kb

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: 33ms
memory: 7940kb

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: 5ms
memory: 6284kb

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: 12ms
memory: 6908kb

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: 24ms
memory: 7836kb

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: 33ms
memory: 7968kb

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: 5ms
memory: 6340kb

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: 14ms
memory: 6860kb

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:

3181458

result:

ok 1 number(s): "3181458"

Test #18:

score: 0
Accepted
time: 24ms
memory: 7380kb

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: 34ms
memory: 7920kb

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: 20ms
memory: 7164kb

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: 30ms
memory: 7948kb

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: 2ms
memory: 6004kb

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: 30ms
memory: 7976kb

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: 0ms
memory: 7848kb

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: 34ms
memory: 7960kb

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: 2ms
memory: 5876kb

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: 30ms
memory: 7916kb

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: 1ms
memory: 7788kb

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"