This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#define int long long
using namespace std;
const int NMAX = 2000;
const int MOD = 1e9 + 7;
int dp[NMAX + 1][NMAX + 1];
int sz[NMAX + 1];
int comb[NMAX + 1][NMAX + 1];
int C(int n, int k){
if(n < 0 || k < 0 || k > n){
return 0;
}
return comb[n][k];
}
signed main(){
comb[0][0] = 1;
for(int i = 1; i <= NMAX; i++){
comb[i][0] = 1;
for(int j = 1; j <= NMAX; j++){
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
}
}
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
sz[i] = n / m;
if(sz[i] <= n % m){
sz[i]++;
}
}
dp[1][sz[1]] = C(n, sz[1]);
int sum = sz[1];
for(int i = 2; i <= m; i++){
sum += sz[i];
for(int j = 0; j <= n; j++){
for(int nw = 0; nw <= sz[i]; nw++){
int r = (sum - j) / 2;
if(r * 2 != sum - j){
continue;
}
if(j - 2 * nw + sz[i] >= 0 && j - 2 * nw + sz[i] <= n){
(dp[i][j] += (((((dp[i - 1][j - 2 * nw + sz[i]] * C(sz[i], nw)) % MOD) * C(n - r, nw)) % MOD) * C(j - 2 * nw + sz[i], sz[i] - nw)) % MOD) %= MOD;
}
}
}
}
int ans = dp[m][0];
int fact = 1, pw = 1;
for(int i = 1; i <= n; i++){
(fact *= i) %= MOD;
(pw *= 2) %= MOD;
}
cout << (((ans * pw) % MOD) * fact) % MOD <<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |