Logo Wy Online Judge

WyOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#446#78. 「NOIP2016」组合数问题Pigsyy10090ms32852kbC++23958b2025-04-24 13:40:222025-04-24 13:40:22

answer

#include <stdio.h>
#include <string.h>
#define max(a,b) a>b?a:b
int main() {
    int i, j, t, nn = 0, mm = 0, k, n[10100], m[10100];
    scanf("%d%d", &t, &k);

    for (i = 1; i <= t; i++) {
        scanf("%d%d", &n[i], &m[i]);
        nn = max(nn, n[i]);
        mm = max(mm, m[i]);
    }

    int c[nn + 1][mm + 1], sum[nn + 1][mm + 1];
    memset(c, 0, sizeof(c));
    memset(sum, 0, sizeof(sum));

    for (i = 0; i <= nn; i++) {
        c[i][0] = 1;
    }

    for (i = 1; i <= nn; i++) {
        for (j = 1; j <= mm; j++) {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;

            if (c[i][j] == 0 && j <= i)
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + 1;
            else
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }

    for (i = 1; i <= t; i++) {
        printf("%d\n", sum[n[i]][m[i]]);
    }

    return 0;
}
源文件, 语言: C++23

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 1ms
memory: 1860kb

input:

1 2
1 1

output:

0

result:

ok "0"

Test #2:

score: 5
Accepted
time: 3ms
memory: 1748kb

input:

8902 3
3 1
3 1
1 2
2 1
3 1
1 1
1 3
3 2
3 1
2 3
2 3
1 1
1 1
2 1
1 2
1 2
2 3
1 3
3 2
1 3
3 3
2 1
1 2
2...

output:

1
1
0
0
1
0
0
2
1
0
0
0
0
0
0
0
0
0
2
0
2
0
0
0
0
0
0
2
0
0
2
0
0
0
1
2
2
0
1
0
0
0
2
0
1
0
0
1
0
0
...

result:

ok 8902 tokens

Test #3:

score: 5
Accepted
time: 2ms
memory: 1948kb

input:

1 4
5 4

output:

2

result:

ok "2"

Test #4:

score: 5
Accepted
time: 4ms
memory: 1860kb

input:

5142 5
4 4
1 2
5 2
6 6
1 1
7 7
6 1
4 4
1 6
6 4
7 1
2 4
3 1
6 2
1 5
7 4
2 3
7 6
3 2
3 4
3 6
3 3
1 6
5...

output:

0
0
2
7
0
9
1
0
0
7
1
0
0
3
0
9
0
9
0
0
0
0
0
4
3
9
0
0
6
0
0
0
9
4
0
5
0
0
0
5
7
0
4
3
0
0
0
9
0
0
...

result:

ok 5142 tokens

Test #5:

score: 5
Accepted
time: 1ms
memory: 1752kb

input:

1 6
8 7

output:

3

result:

ok "3"

Test #6:

score: 5
Accepted
time: 3ms
memory: 1820kb

input:

8952 7
5 3
4 8
9 7
6 10
6 10
2 1
2 8
4 3
8 10
5 7
5 8
6 7
9 2
7 9
8 4
9 7
5 10
9 1
1 10
3 10
2 4
3 6...

output:

0
0
15
0
0
0
0
0
11
0
0
0
3
6
7
15
0
1
0
0
0
0
1
0
0
0
0
5
0
6
0
0
6
0
0
0
0
0
18
0
0
0
6
0
3
6
0
18...

result:

ok 8952 tokens

Test #7:

score: 5
Accepted
time: 0ms
memory: 1880kb

input:

1 8
17 69

output:

29

result:

ok "29"

Test #8:

score: 5
Accepted
time: 2ms
memory: 2008kb

input:

6041 9
19 72
18 28
8 80
20 6
20 33
4 34
18 1
7 16
20 55
9 83
3 70
9 93
3 2
13 60
13 16
4 45
3 81
8 4...

output:

36
30
0
15
36
0
2
0
36
6
0
6
0
15
15
0
0
0
0
0
18
0
6
15
17
0
15
18
0
15
18
13
0
0
15
0
0
33
0
18
0
...

result:

ok 6041 tokens

Test #9:

score: 5
Accepted
time: 1ms
memory: 1912kb

input:

1 10
21 1885

output:

56

result:

ok "56"

Test #10:

score: 5
Accepted
time: 3ms
memory: 1948kb

input:

7425 11
22 1256
14 889
10 437
19 1636
10 1261
22 1673
23 90
10 294
24 1945
14 746
13 316
12 712
16 6...

output:

75
34
0
54
0
75
93
0
109
34
27
19
45
27
34
93
54
75
55
45
52
75
10
27
40
49
55
27
0
55
40
52
40
10
4...

result:

ok 7425 tokens

Test #11:

score: 5
Accepted
time: 1ms
memory: 1748kb

input:

1 12
49 17

output:

208

result:

ok "208"

Test #12:

score: 5
Accepted
time: 5ms
memory: 1820kb

input:

7806 13
41 4
31 7
33 20
52 8
58 9
37 16
36 1
47 2
55 13
47 18
33 19
37 3
30 5
52 8
46 17
43 10
59 2
...

output:

29
55
174
116
177
162
2
9
276
258
167
12
30
116
244
150
12
183
42
336
156
24
336
243
72
285
56
84
13...

result:

ok 7806 tokens

Test #13:

score: 5
Accepted
time: 1ms
memory: 1756kb

input:

1 14
72 24

output:

544

result:

ok "544"

Test #14:

score: 5
Accepted
time: 5ms
memory: 1804kb

input:

6040 15
79 15
68 15
71 7
65 21
88 10
77 23
69 21
57 22
74 8
76 1
54 16
62 2
92 11
70 17
73 9
92 5
84...

output:

356
309
104
491
226
649
513
421
144
5
240
20
274
380
160
98
602
225
356
182
158
288
438
101
611
525
...

result:

ok 6040 tokens

Test #15:

score: 5
Accepted
time: 1ms
memory: 1816kb

input:

1 16
99 60

output:

1054

result:

ok "1054"

Test #16:

score: 5
Accepted
time: 7ms
memory: 1912kb

input:

8972 17
63 29
65 56
89 28
92 9
84 32
90 8
81 11
89 9
59 45
73 47
89 23
85 34
80 48
93 41
96 54
64 50...

output:

558
813
857
224
904
177
264
215
687
996
697
984
1149
1252
1614
807
665
1216
454
15
449
445
135
786
7...

result:

ok 8972 tokens

Test #17:

score: 5
Accepted
time: 4ms
memory: 2372kb

input:

1 18
1252 87

output:

50793

result:

ok "50793"

Test #18:

score: 5
Accepted
time: 5ms
memory: 3268kb

input:

6342 19
1738 88
1657 23
1422 78
1758 88
1582 32
1614 54
1701 84
1621 15
1488 46
1466 31
1745 82
1475...

output:

75121
15986
53864
75917
22249
41965
69518
10164
30948
19630
69393
462
51711
28113
35412
33453
73534
...

result:

ok 6342 tokens

Test #19:

score: 5
Accepted
time: 21ms
memory: 20168kb

input:

1 20
1692 1406

output:

994718

result:

ok "994718"

Test #20:

score: 5
Accepted
time: 20ms
memory: 32852kb

input:

5814 21
1083 623
1647 838
1233 1307
1438 1052
1001 1012
1665 1725
1416 1916
1900 1258
1981 1943
1642...

output:

331596
721910
528906
667760
338812
970793
691552
1144521
1398891
630420
513040
1101938
571061
412078...

result:

ok 5814 tokens
中文 English

鲁ICP备2025150228号

服务器时间: 2025-04-30 07:06:36 | 开源项目