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 <bits/stdc++.h>
#define int long long
using namespace std;
int dp[2001][2001];
int a[2001], s[2001];
int c[2001][2001];
const int MOD = 1e9 + 7;
void chadd(int& x, int y) { x += y; x %= MOD; }
int C(int n, int r){
if(r < 0 || r > n) return 0;
return c[n][r];
}
int32_t main(){
int N, M; cin >> N >> M;
for(int i = 0; i < M; i++) a[i] = (N * 2 + i) / M;
for(int i = 0; i < M; i++) s[i + 1] = s[i] + a[i];
dp[0][0] = 1;
for(int i = 0; i <= 2000; i++){
c[i][0] = c[i][i] = 1;
for(int j = 1; j < i; j++){
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
for(int i = 0; i < M; i++){
for(int j = 0; j <= N; j++){
for(int k = 0; k <= a[i]; k++){
int j2 = j + (a[i] - k) - k; if(j2 < 0 || j2 > N) continue;
chadd(dp[i + 1][j2], dp[i][j] * C(j, k) % MOD * C(N - (s[i] + j) / 2, a[i] - k) % MOD);
}
}
}
int ans = dp[M][0];
for(int i = 0; i < N; i++){
ans = ans * 2 % MOD;
}
for(int i = 0; i < M; i++){
for(int j = 1; j <= a[i]; j++){
ans = ans * j % MOD;
}
}
cout << ans << endl;
}
# | 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... |