답안 #1038436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038436	2024-07-29T19:32:28 Z	andrei_c1	NoM (RMI21_nom)	C++17	100 / 100	91 ms	60500 KB

Main

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

const int kMod = 1e9 + 7;

void addSelf(int &x, int y) {
	x += y;
	if(x >= kMod) {
		x -= kMod;
	}
}

int add(int x, int y) {
	addSelf(x, y);
	return x;
}

void multSelf(int &x, int y) {
	x = (ll)x * y % kMod;
}

int mult(int x, int y) {
	multSelf(x, y);
	return x;
}

const int kN = 2000;

int dp[2][2 * kN + 1], comb[2 * kN + 1][2 * kN + 1];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m);
	for(int i = 0; i < 2 * n; i++) {
		cnt[i % m]++;
	}
	comb[0][0] = 1;
	for(int i = 1; i <= 2 * n; i++) {
		comb[i][0] = comb[i][i] = 1;
		for(int j = 1; j < i; j++) {
			comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
		}
	}
	int sum = cnt[0];
	dp[0][sum] = 1;
	for(int i = 1; i < m; i++) {
		int fact = 1;
		for(int j = 0; j <= cnt[i]; j++) {
			for(int k = j; k <= sum; k++) {
				int ways = dp[(i - 1) & 1][k];
				multSelf(ways, comb[cnt[i]][j]);
				multSelf(ways, comb[k][j]);
				multSelf(ways, fact);
				addSelf(dp[i & 1][k + cnt[i] - 2 * j], ways);
			}
			multSelf(fact, j + 1);
		}
		for(int k = 0; k <= sum; k++) {
			dp[(i - 1) & 1][k] = 0;
		}
		sum += cnt[i];
	}
	int res = dp[(m - 1) & 1][0];
	for(int i = 1; i <= n; i++) {
		multSelf(res, 2);
		multSelf(res, i);
	}
	cout << res << '\n';
	return 0;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	2560 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	0 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2508 KB	Output is correct
18	Correct	0 ms	2396 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct

Subtask #3
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	2560 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	0 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2508 KB	Output is correct
18	Correct	0 ms	2396 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	6492 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	2 ms	8540 KB	Output is correct
23	Correct	2 ms	8540 KB	Output is correct
24	Correct	2 ms	10588 KB	Output is correct
25	Correct	2 ms	8540 KB	Output is correct
26	Correct	2 ms	8540 KB	Output is correct
27	Correct	3 ms	10588 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	2560 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	0 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2508 KB	Output is correct
18	Correct	0 ms	2396 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	6492 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	2 ms	8540 KB	Output is correct
23	Correct	2 ms	8540 KB	Output is correct
24	Correct	2 ms	10588 KB	Output is correct
25	Correct	2 ms	8540 KB	Output is correct
26	Correct	2 ms	8540 KB	Output is correct
27	Correct	3 ms	10588 KB	Output is correct
28	Correct	7 ms	20828 KB	Output is correct
29	Correct	9 ms	20828 KB	Output is correct
30	Correct	11 ms	20828 KB	Output is correct
31	Correct	7 ms	20828 KB	Output is correct
32	Correct	10 ms	23072 KB	Output is correct
33	Correct	12 ms	22872 KB	Output is correct
34	Correct	18 ms	29256 KB	Output is correct

Subtask #5
48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4444 KB	Output is correct
12	Correct	1 ms	2560 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	0 ms	2396 KB	Output is correct
15	Correct	1 ms	2392 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2508 KB	Output is correct
18	Correct	0 ms	2396 KB	Output is correct
19	Correct	1 ms	4444 KB	Output is correct
20	Correct	1 ms	6492 KB	Output is correct
21	Correct	1 ms	6492 KB	Output is correct
22	Correct	2 ms	8540 KB	Output is correct
23	Correct	2 ms	8540 KB	Output is correct
24	Correct	2 ms	10588 KB	Output is correct
25	Correct	2 ms	8540 KB	Output is correct
26	Correct	2 ms	8540 KB	Output is correct
27	Correct	3 ms	10588 KB	Output is correct
28	Correct	7 ms	20828 KB	Output is correct
29	Correct	9 ms	20828 KB	Output is correct
30	Correct	11 ms	20828 KB	Output is correct
31	Correct	7 ms	20828 KB	Output is correct
32	Correct	10 ms	23072 KB	Output is correct
33	Correct	12 ms	22872 KB	Output is correct
34	Correct	18 ms	29256 KB	Output is correct
35	Correct	40 ms	49496 KB	Output is correct
36	Correct	70 ms	53340 KB	Output is correct
37	Correct	39 ms	48476 KB	Output is correct
38	Correct	53 ms	49568 KB	Output is correct
39	Correct	55 ms	47704 KB	Output is correct
40	Correct	91 ms	60500 KB	Output is correct

답안 #1038436

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 18.0 / 18.0

Subtask #5 48.0 / 48.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
13.0 / 13.0

Subtask #4
18.0 / 18.0

Subtask #5
48.0 / 48.0