| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1038419 |
2024-07-29T19:08:12 Z |
andrei_c1 |
NoM (RMI21_nom) |
C++17 |
|
294 ms |
604 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;
}
int fact(int n) {
static vector<int> data(1, 1);
for(int i = data.size(); i <= n; i++) {
data.emplace_back(mult(data[i - 1], i));
}
return data[n];
}
int inv(int n) {
static vector<int> data(2, 1);
for(int i = data.size(); i <= n; i++) {
data.emplace_back(mult(data[kMod % i], kMod - kMod / i));
}
return data[n];
}
int ifact(int n) {
static vector<int> data(2, 1);
for(int i = data.size(); i <= n; i++) {
data.emplace_back(mult(data[i - 1], inv(i)));
}
return data[n];
}
int comb(int n, int k) {
if(k > n) return 0;
return mult(fact(n), mult(ifact(k), ifact(n - k)));
}
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]++;
}
int sum = cnt[0];
vector<int> dp(sum + 1);
dp[sum] = 1;
for(int i = 1; i < m; i++) {
vector<int> ndp(sum + cnt[i] + 1);
for(int j = 0; j <= cnt[i]; j++) {
for(int k = j; k <= sum; k++) {
int ways = dp[k];
multSelf(ways, comb(cnt[i], j));
multSelf(ways, comb(k, j));
multSelf(ways, fact(j));
addSelf(ndp[k + cnt[i] - 2 * j], ways);
}
}
dp = ndp;
sum += cnt[i];
}
int res = mult(dp[0], fact(n));
for(int i = 0; i < n; i++) {
multSelf(res, 2);
}
cout << res << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
0 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 |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
456 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
456 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
2 ms |
604 KB |
Output is correct |
| 21 |
Correct |
2 ms |
348 KB |
Output is correct |
| 22 |
Correct |
5 ms |
576 KB |
Output is correct |
| 23 |
Correct |
3 ms |
348 KB |
Output is correct |
| 24 |
Correct |
6 ms |
348 KB |
Output is correct |
| 25 |
Correct |
5 ms |
348 KB |
Output is correct |
| 26 |
Correct |
3 ms |
348 KB |
Output is correct |
| 27 |
Correct |
6 ms |
576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
456 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
2 ms |
604 KB |
Output is correct |
| 21 |
Correct |
2 ms |
348 KB |
Output is correct |
| 22 |
Correct |
5 ms |
576 KB |
Output is correct |
| 23 |
Correct |
3 ms |
348 KB |
Output is correct |
| 24 |
Correct |
6 ms |
348 KB |
Output is correct |
| 25 |
Correct |
5 ms |
348 KB |
Output is correct |
| 26 |
Correct |
3 ms |
348 KB |
Output is correct |
| 27 |
Correct |
6 ms |
576 KB |
Output is correct |
| 28 |
Correct |
16 ms |
492 KB |
Output is correct |
| 29 |
Correct |
25 ms |
544 KB |
Output is correct |
| 30 |
Correct |
31 ms |
348 KB |
Output is correct |
| 31 |
Correct |
17 ms |
348 KB |
Output is correct |
| 32 |
Correct |
27 ms |
576 KB |
Output is correct |
| 33 |
Correct |
35 ms |
348 KB |
Output is correct |
| 34 |
Correct |
61 ms |
584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
348 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
1 ms |
348 KB |
Output is correct |
| 15 |
Correct |
1 ms |
348 KB |
Output is correct |
| 16 |
Correct |
1 ms |
348 KB |
Output is correct |
| 17 |
Correct |
1 ms |
348 KB |
Output is correct |
| 18 |
Correct |
0 ms |
456 KB |
Output is correct |
| 19 |
Correct |
0 ms |
348 KB |
Output is correct |
| 20 |
Correct |
2 ms |
604 KB |
Output is correct |
| 21 |
Correct |
2 ms |
348 KB |
Output is correct |
| 22 |
Correct |
5 ms |
576 KB |
Output is correct |
| 23 |
Correct |
3 ms |
348 KB |
Output is correct |
| 24 |
Correct |
6 ms |
348 KB |
Output is correct |
| 25 |
Correct |
5 ms |
348 KB |
Output is correct |
| 26 |
Correct |
3 ms |
348 KB |
Output is correct |
| 27 |
Correct |
6 ms |
576 KB |
Output is correct |
| 28 |
Correct |
16 ms |
492 KB |
Output is correct |
| 29 |
Correct |
25 ms |
544 KB |
Output is correct |
| 30 |
Correct |
31 ms |
348 KB |
Output is correct |
| 31 |
Correct |
17 ms |
348 KB |
Output is correct |
| 32 |
Correct |
27 ms |
576 KB |
Output is correct |
| 33 |
Correct |
35 ms |
348 KB |
Output is correct |
| 34 |
Correct |
61 ms |
584 KB |
Output is correct |
| 35 |
Correct |
135 ms |
348 KB |
Output is correct |
| 36 |
Correct |
241 ms |
596 KB |
Output is correct |
| 37 |
Correct |
116 ms |
500 KB |
Output is correct |
| 38 |
Correct |
162 ms |
596 KB |
Output is correct |
| 39 |
Correct |
185 ms |
576 KB |
Output is correct |
| 40 |
Correct |
294 ms |
604 KB |
Output is correct |
