| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038436 |
2024-07-29T19:32:28 Z |
andrei_c1 |
NoM (RMI21_nom) |
C++17 |
|
91 ms |
60500 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
