| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 857761 |
2023-10-06T21:53:14 Z |
divad |
NoM (RMI21_nom) |
C++14 |
|
9 ms |
63324 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 2e3+2;
int n,m,cnt[NMAX];
/// dp[i][j] = cate imperecheri pot obtine cu primele i resturi si sa ramana j neimperecheata
struct Mint{
int val;
Mint(){
val = 0;
}
Mint(int _val){
val = _val%MOD;
}
Mint operator * (Mint oth) {
return (val * oth.val);
}
Mint operator * (int oth) {
oth %= MOD;
return (val * oth);
}
Mint operator + (Mint oth) {
return (val + oth.val);
}
Mint operator - (Mint oth) {
return (val + MOD - oth.val);
}
Mint operator = (int oth){
val = oth;
return *this;
}
Mint operator += (Mint oth){
val += oth.val;
return *this;
}
} fact[2*NMAX], inv[2*NMAX], dp[NMAX][2*NMAX];
Mint lgput(int n, int a){
if(a == 0){
return 1;
}else{
if(a%2 == 0){
Mint val = lgput(n, a/2);
return val*val;
}else{
return lgput(n, a-1)*n;
}
}
}
Mint comb(int n, int m){
return fact[n]*inv[n-m]*inv[m];
}
Mint aranj(int n, int m){
return fact[n]*inv[n-m];
}
signed main()
{
fact[0] = 1;
for(int i = 1; i < NMAX*2; i++){
fact[i] = fact[i-1]*i;
}
inv[NMAX*2-1] = lgput(fact[NMAX*2-1].val, MOD-2);
for(int i = NMAX*2-2; i >= 0; i--){
inv[i] = inv[i+1]*(i+1);
}
cin >> n >> m;
for(int i = 1; i <= 2*n; i++){
cnt[i%m]++;
}
dp[0][cnt[0]] = 1;
int maxi = cnt[0];
for(int i = 1; i < m; i++){
for(int k = 0; k <= cnt[i]; k++){
for(int j = k; j <= maxi; j++){
/// (i-1, j) -> (i, j-k+(cnt[i]-k))
dp[i][j-k+(cnt[i]-k)] += dp[i-1][j]*comb(cnt[i], k)*aranj(j, k);
}
}
maxi += cnt[i];
}
dp[m-1][0] = dp[m-1][0]*fact[n];
dp[m-1][0] = dp[m-1][0]*lgput(2, n);
cout << dp[m-1][0].val;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
63180 KB |
Output is correct |
| 3 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 4 |
Correct |
8 ms |
63324 KB |
Output is correct |
| 5 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 6 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 8 |
Correct |
8 ms |
63064 KB |
Output is correct |
| 9 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 10 |
Correct |
7 ms |
63068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
63180 KB |
Output is correct |
| 3 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 4 |
Correct |
8 ms |
63324 KB |
Output is correct |
| 5 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 6 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 8 |
Correct |
8 ms |
63064 KB |
Output is correct |
| 9 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 10 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 11 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 12 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 13 |
Correct |
8 ms |
63148 KB |
Output is correct |
| 14 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 15 |
Correct |
7 ms |
63004 KB |
Output is correct |
| 16 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 18 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 19 |
Correct |
8 ms |
63164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
63180 KB |
Output is correct |
| 3 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 4 |
Correct |
8 ms |
63324 KB |
Output is correct |
| 5 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 6 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 8 |
Correct |
8 ms |
63064 KB |
Output is correct |
| 9 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 10 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 11 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 12 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 13 |
Correct |
8 ms |
63148 KB |
Output is correct |
| 14 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 15 |
Correct |
7 ms |
63004 KB |
Output is correct |
| 16 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 18 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 19 |
Correct |
8 ms |
63164 KB |
Output is correct |
| 20 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 21 |
Correct |
8 ms |
63224 KB |
Output is correct |
| 22 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 23 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 24 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 25 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 26 |
Incorrect |
8 ms |
63068 KB |
Output isn't correct |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
63180 KB |
Output is correct |
| 3 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 4 |
Correct |
8 ms |
63324 KB |
Output is correct |
| 5 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 6 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 8 |
Correct |
8 ms |
63064 KB |
Output is correct |
| 9 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 10 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 11 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 12 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 13 |
Correct |
8 ms |
63148 KB |
Output is correct |
| 14 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 15 |
Correct |
7 ms |
63004 KB |
Output is correct |
| 16 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 18 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 19 |
Correct |
8 ms |
63164 KB |
Output is correct |
| 20 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 21 |
Correct |
8 ms |
63224 KB |
Output is correct |
| 22 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 23 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 24 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 25 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 26 |
Incorrect |
8 ms |
63068 KB |
Output isn't correct |
| 27 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 2 |
Correct |
7 ms |
63180 KB |
Output is correct |
| 3 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 4 |
Correct |
8 ms |
63324 KB |
Output is correct |
| 5 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 6 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 7 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 8 |
Correct |
8 ms |
63064 KB |
Output is correct |
| 9 |
Correct |
7 ms |
63216 KB |
Output is correct |
| 10 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 11 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 12 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 13 |
Correct |
8 ms |
63148 KB |
Output is correct |
| 14 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 15 |
Correct |
7 ms |
63004 KB |
Output is correct |
| 16 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 17 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 18 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 19 |
Correct |
8 ms |
63164 KB |
Output is correct |
| 20 |
Correct |
7 ms |
63068 KB |
Output is correct |
| 21 |
Correct |
8 ms |
63224 KB |
Output is correct |
| 22 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 23 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 24 |
Correct |
9 ms |
63068 KB |
Output is correct |
| 25 |
Correct |
8 ms |
63068 KB |
Output is correct |
| 26 |
Incorrect |
8 ms |
63068 KB |
Output isn't correct |
| 27 |
Halted |
0 ms |
0 KB |
- |
