QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#511831#8323. 虫洞pavement#8 622ms35400kbC++171.5kb2024-08-10 11:45:272024-08-10 11:45:27

Judging History

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

  • [2024-08-10 11:45:27]
  • 评测
  • 测评结果：8
  • 用时：622ms
  • 内存：35400kb
查看
  • [2024-08-10 11:45:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// solve m = 0, k = 1

using ll = long long;

const int MOD = 998244353;
int c, n, m, k, to[2005], fac[2005], inv_fac[2005], mem[2005][2005], memf[2005][2005];

int nck(int n, int k) {
	return (ll)fac[n] * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

int f(int x, int y) {
	if (x == 0) {
		return 1;
	}
	if (memf[x][y] != -1) {
		return memf[x][y];
	}
	return memf[x][y] = (ll)f(x - y, y) * nck(x, y) % MOD;
}

int exp_mod(int a, int b) {
	int r = 1;
	while (b) {
		if (b % 2 == 1) {
			r = (ll)r * a % MOD;
		}
		a = (ll)a * a % MOD;
		b /= 2;
	}
	return r;
}

int dp(int x, int lim) {
	if (x == 0) {
		return 1;
	}
	if (lim <= 0) {
		return 0;
	}
	if (mem[x][lim] != -1) {
		return mem[x][lim];
	}
	int ret = dp(x, lim - 1);
	for (int reps = 1; reps * lim <= x; reps++) {
		ret += (ll)dp(x - reps * lim, lim - 1) * nck(x, reps * lim) % MOD * f(reps * lim, lim) % MOD * inv_fac[reps] % MOD * exp_mod(fac[lim - 1], reps) % MOD;
		if (ret >= MOD) {
			ret -= MOD;
		}
	}
	return mem[x][lim] = ret;
}

int main() {
	memset(mem, -1, sizeof mem);
	memset(memf, -1, sizeof memf);
	fac[0] = 1;
	inv_fac[0] = 1;
	for (int i = 1; i <= 2000; i++) {
		fac[i] = (ll)fac[i - 1] * i % MOD;
		inv_fac[i] = exp_mod(fac[i], MOD - 2);
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> c >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1, u, v, w; j <= m; j++) {
			cin >> u >> v >> w;
			to[u] = v;
		}
	}
	cout << dp(n, n) << '\n';
}
源文件, 语言: C++17

详细


Pretests


Final Tests

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 35064kb

input:

1 4 1 2
2 2 1
3 3 1
4 4 1
1 1 1

output:

24

result:

wrong answer 1st lines differ - expected: '120', found: '24'

Test #2:

score: 0
Wrong Answer
time: 0ms
memory: 35060kb

input:

2 5 2 2
4 1 1
2 5 2
1 4 2
5 3 2
1 4 1
4 1 2
3 2 2
2 5 1
5 3 1
3 2 1

output:

120

result:

wrong answer 1st lines differ - expected: '36', found: '120'

Test #3:

score: 0
Wrong Answer
time: 0ms
memory: 35048kb

input:

3 5 3 3
1 1 2
2 2 2
5 5 3
4 4 2
4 4 3
1 1 1
5 5 2
4 4 1
3 3 2
2 2 3
1 1 3
2 2 1
5 3 1
3 3 3
3 5 1

output:

120

result:

wrong answer 1st lines differ - expected: '384', found: '120'

Test #4:

score: 0
Wrong Answer
time: 3ms
memory: 35128kb

input:

4 5 3 3
5 4 1
5 5 2
5 5 3
2 2 1
2 2 2
1 1 3
2 2 3
4 4 2
1 1 2
3 3 2
1 5 1
4 1 1
3 3 1
4 4 3
3 3 3

output:

120

result:

wrong answer 1st lines differ - expected: '216', found: '120'

Test #5:

score: 4
Accepted
time: 409ms
memory: 35400kb

input:

5 1996 0 1

output:

348407495

result:

ok single line: '348407495'

Test #6:

score: 4
Accepted
time: 410ms
memory: 35400kb

input:

6 1997 0 1

output:

991697827

result:

ok single line: '991697827'

Test #7:

score: 0
Wrong Answer
time: 2ms
memory: 35132kb

input:

7 97 1 1
97 64 1
49 11 1
1 1 1
89 89 1
48 40 1
18 76 1
53 53 1
50 50 1
45 45 1
82 95 1
62 9 1
72 72 1
78 78 1
52 24 1
91 91 1
66 66 1
36 36 1
85 85 1
22 65 1
30 30 1
57 57 1
95 19 1
67 67 1
41 41 1
34 13 1
65 4 1
5 70 1
23 23 1
92 92 1
31 8 1
4 22 1
35 35 1
7 7 1
75 75 1
12 12 1
90 90 1
37 44 1
19 8...

output:

624186735

result:

wrong answer 1st lines differ - expected: '472345743', found: '624186735'

Test #8:

score: 0
Wrong Answer
time: 4ms
memory: 35048kb

input:

8 96 1 1
74 63 1
57 57 1
21 21 1
22 22 1
55 55 1
85 6 1
92 3 1
62 90 1
12 12 1
70 4 1
89 35 1
6 28 1
61 80 1
23 23 1
66 66 1
31 87 1
80 10 1
38 47 1
75 76 1
50 37 1
95 68 1
56 56 1
20 20 1
1 45 1
18 18 1
91 91 1
64 85 1
60 79 1
19 2 1
30 65 1
40 40 1
96 67 1
34 34 1
87 31 1
94 94 1
52 92 1
16 41 1
2...

output:

984096910

result:

wrong answer 1st lines differ - expected: '386508477', found: '984096910'

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 35052kb

input:

9 98 10 1
49 47 8
25 25 2
72 72 3
70 14 10
57 57 1
55 55 3
68 68 3
66 66 9
6 6 5
50 56 8
25 25 3
3 3 6
32 32 2
63 63 1
84 84 8
91 91 9
21 21 8
2 2 7
74 74 2
14 14 5
93 93 9
92 92 3
45 45 6
38 38 3
86 86 7
57 57 5
7 7 1
52 52 3
66 66 1
27 27 9
3 3 3
91 91 2
72 72 10
5 5 8
63 63 2
45 45 8
44 44 7
20 2...

output:

277394497

result:

wrong answer 1st lines differ - expected: '493819619', found: '277394497'

Test #10:

score: 0
Wrong Answer
time: 7ms
memory: 35060kb

input:

10 97 9 1
83 83 8
66 66 6
82 82 3
86 86 2
41 25 9
49 49 5
53 53 2
29 29 7
43 43 5
80 80 3
36 97 8
47 47 7
71 71 4
75 46 3
82 82 1
70 70 2
64 64 9
49 49 2
23 23 8
17 17 9
38 38 1
37 37 5
28 28 1
90 90 6
26 26 9
56 56 5
7 7 1
43 43 4
15 15 7
21 21 5
39 39 6
7 7 8
94 94 4
42 42 6
16 75 6
44 44 6
16 75 ...

output:

624186735

result:

wrong answer 1st lines differ - expected: '919203092', found: '624186735'

Test #11:

score: 0
Wrong Answer
time: 3ms
memory: 35044kb

input:

11 99 6 933
84 84 3
22 12 1
80 80 6
89 89 2
14 14 2
34 34 2
4 4 3
33 33 3
91 36 2
44 39 6
18 18 3
9 9 4
85 85 3
53 53 3
61 61 5
76 24 1
89 89 4
9 9 2
8 8 2
30 30 1
27 27 1
71 71 2
77 77 4
85 85 5
62 62 3
50 50 3
64 64 4
7 7 2
93 93 1
11 11 3
91 91 4
16 16 1
34 34 4
40 23 3
32 32 3
33 33 4
59 59 3
60...

output:

509457672

result:

wrong answer 1st lines differ - expected: '593017136', found: '509457672'

Test #12:

score: 0
Wrong Answer
time: 3ms
memory: 35008kb

input:

12 100 9 914
62 62 2
10 79 6
23 23 4
54 54 7
91 91 2
38 38 8
18 18 6
82 10 3
81 81 7
45 45 1
77 77 1
59 59 6
65 84 7
94 75 3
85 85 4
57 57 7
84 84 9
18 18 9
1 1 2
7 7 6
31 31 5
2 2 1
75 75 4
29 29 6
84 30 1
53 53 9
81 81 8
88 88 8
89 89 3
22 22 3
64 64 4
15 15 2
88 88 2
74 74 5
95 95 7
43 43 9
19 92...

output:

35305197

result:

wrong answer 1st lines differ - expected: '591139293', found: '35305197'

Test #13:

score: 0
Wrong Answer
time: 4ms
memory: 35064kb

input:

13 99 9 908
80 80 8
83 83 1
4 4 1
52 52 4
18 18 8
58 58 1
78 78 4
98 98 3
68 68 3
83 83 9
45 45 2
70 70 6
73 73 1
21 21 9
1 1 8
46 6 7
26 26 3
64 64 6
93 93 4
65 65 6
16 16 5
29 29 1
90 90 8
42 42 4
89 89 2
74 74 9
37 37 9
72 72 7
67 67 6
27 84 6
9 9 2
53 49 8
94 94 7
56 56 6
54 54 2
67 67 3
18 18 2...

output:

509457672

result:

wrong answer 1st lines differ - expected: '605317308', found: '509457672'

Test #14:

score: 0
Wrong Answer
time: 0ms
memory: 35068kb

input:

14 100 9 856
85 85 4
78 78 3
34 34 8
74 74 3
71 71 5
97 97 4
65 65 5
61 61 1
1 51 4
79 79 7
94 94 5
47 47 5
71 71 9
63 63 3
34 34 1
97 97 6
53 53 9
17 17 8
12 42 8
11 11 1
10 10 3
23 23 6
33 33 7
77 77 1
25 25 3
67 67 9
81 81 2
42 42 2
1 1 9
36 43 4
90 90 7
54 54 6
62 62 7
40 41 6
85 85 5
41 41 4
52...

output:

35305197

result:

wrong answer 1st lines differ - expected: '512859775', found: '35305197'

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 35056kb

input:

15 99 0 999999051080524

output:

509457672

result:

wrong answer 1st lines differ - expected: '884029302', found: '509457672'

Test #16:

score: 0
Wrong Answer
time: 3ms
memory: 35024kb

input:

16 99 0 999999708304723

output:

509457672

result:

wrong answer 1st lines differ - expected: '916561743', found: '509457672'

Test #17:

score: 0
Runtime Error

input:

17 97 9 999998575885466
6 6 3
85 85 3
53 53 4
66 66 3
30 30 2
25 25 8
41 55 1
60 60 2
78 78 4
34 34 1
71 71 3
72 72 9
57 57 5
81 20 1
18 18 9
40 40 9
74 74 2
46 46 7
63 63 2
37 37 1
95 95 8
84 84 7
92 92 3
47 47 8
28 28 3
60 60 3
55 55 7
7 7 9
24 24 2
57 57 3
85 85 4
17 17 4
34 34 3
82 82 7
3 30 1
4...

output:

result:

Test #18:

score: 0
Runtime Error

input:

18 98 8 999999221481775
95 95 6
86 86 6
95 95 7
15 15 8
42 42 8
52 52 2
24 24 8
35 35 6
37 37 7
2 2 3
62 62 7
50 50 3
19 19 4
76 76 2
14 14 6
95 95 1
9 9 1
37 37 2
58 58 5
43 43 6
44 44 7
60 60 7
7 81 8
93 68 5
88 88 3
63 63 1
5 5 8
43 43 3
94 94 8
4 4 7
94 94 4
32 32 2
26 78 5
85 60 5
46 3 5
96 96 ...

output:

result:

Test #19:

score: 0
Runtime Error

input:

19 98 10 999998787947143
85 85 1
93 93 5
79 29 10
73 73 10
80 80 2
10 10 10
36 36 5
37 37 5
66 66 2
10 10 8
29 79 8
74 74 3
71 71 1
95 95 2
13 13 5
64 64 10
10 10 3
47 47 2
53 53 6
30 30 5
27 27 6
54 39 9
36 36 2
41 61 8
17 55 8
49 49 10
98 98 1
37 33 8
36 36 1
75 75 7
31 31 3
45 45 8
74 74 6
13 13 ...

output:

result:

Test #20:

score: 0
Wrong Answer
time: 622ms
memory: 35316kb

input:

20 1998 997 82
1362 1362 148
1559 1559 279
594 594 203
63 63 272
1170 1170 713
1501 1501 474
879 879 956
255 255 693
1818 1818 612
1968 1968 586
417 417 823
1565 1565 786
1586 1586 667
1780 1780 974
1208 1208 718
696 696 73
1188 1188 739
870 870 290
1797 1797 830
1904 1904 511
186 186 98
991 991 715...

output:

895461994

result:

wrong answer 1st lines differ - expected: '244392238', found: '895461994'

Test #21:

score: 0
Wrong Answer
time: 618ms
memory: 35276kb

input:

21 1999 999 92
814 814 865
526 526 225
565 565 653
1861 1861 598
781 781 191
1670 1670 900
712 712 883
900 900 677
1503 1503 652
969 969 210
1204 1204 46
336 336 836
1439 1439 599
773 773 303
887 887 174
1260 1260 465
705 705 846
460 460 701
1712 1712 168
1012 1012 596
1160 1160 547
55 55 353
1148 1...

output:

176401077

result:

wrong answer 1st lines differ - expected: '357240500', found: '176401077'

Test #22:

score: 0
Runtime Error

input:

22 2000 999 999998064966521
353 353 378
1290 1290 712
1752 1752 841
61 61 404
1847 1847 264
1187 1187 671
519 519 694
1985 1985 800
591 591 558
648 648 746
1398 1398 876
401 401 996
1050 1050 714
841 841 70
1657 1657 149
1108 1108 672
669 669 508
861 861 305
1445 1445 685
1121 1121 32
1616 1616 586
...

output:

result:

Test #23:

score: 0
Runtime Error

input:

23 1998 1000 999997365774803
524 524 528
1774 1774 517
635 635 172
1914 1914 242
1727 1727 876
1202 1202 227
841 841 219
1348 1348 88
38 38 326
246 246 485
1182 1182 492
860 860 290
288 288 596
1285 1285 389
31 31 777
1042 1042 522
1453 1453 168
43 43 64
1255 1255 375
1616 1616 317
1314 1314 942
292...

output:

result:

Test #24:

score: 0
Runtime Error

input:

24 1997 998 999998752894888
762 762 692
128 128 951
1389 1389 894
914 914 790
668 668 65
1632 1632 372
828 828 542
788 788 136
1132 1132 689
1911 1911 376
326 326 604
1581 1581 708
1603 1603 197
954 954 864
1885 1885 597
1090 1090 214
770 770 785
880 880 722
1109 1109 33
1423 1423 80
855 855 429
198...

output:

result:

Test #25:

score: 0
Runtime Error

input:

25 1999 997 999996902277957
10 10 119
1934 1934 983
1825 1825 193
1483 1483 320
1010 1010 349
717 717 990
577 577 254
975 975 448
1366 1366 39
1515 1515 30
446 446 194
580 580 476
1092 1092 6
119 119 906
778 778 651
1444 1444 446
819 819 123
1566 1566 61
855 855 256
1312 1312 717
1303 1303 821
1456 ...

output:

result:
English 繁體中文 简体中文

服务器时间: 2024-12-05 01:57:17 | 开源项目