Submission #858222

#TimeUsernameProblemLanguageResultExecution timeMemory
858222thangdz2k7NoM (RMI21_nom)C++17
34 / 100
517 ms28968 KiB
#include <bits/stdc++.h> #define ii pair <int, int> #define F first #define S second using namespace std; const int mod = 1e9 + 7; const int N = 4e3 + 5; void add(int &a, int b){ a += b; if (a >= mod) a -= mod; if (a < 0) a += mod; } int mu(int a, int b){ if (b == 0) return 1; if (b % 2 == 1) return 1ll * mu(a, b - 1) * a % mod; int c = mu(a, b / 2); return 1ll * c * c % mod; } int dp[N][N], C[N][N]; int n, m; int gt[N], re_2[N]; int c(int b, int a){ return 1ll * (1ll * gt[a] * mu(gt[b], mod - 2) % mod) * mu(gt[a - b], mod - 2) % mod; } void solve(){ cin >> n >> m; gt[0] = 1; for (int i = 1; i <= 2 * n; ++ i) gt[i] = 1ll * gt[i - 1] * i % mod; int kk = mu(2, mod - 2); re_2[0] = 1; for (int i = 1; i <= n; ++ i) re_2[i] = 1ll * re_2[i - 1] * kk % mod; for (int i = 0; i <= 2 * n; ++ i) for (int j = 0; j <= i; ++ j) C[j][i] = c(j, i); dp[0][0] = 1; for (int i = 1; i <= m; ++ i){ int val = (2 * n - i) / m + 1; for (int j = 0; j <= n; ++ j){ //dp[i][j] = dp[i - 1][j]; for (int k = 0; k <= min(j, val / 2); ++ k){ int zk = 1ll * dp[i - 1][j - k] * C[2 * k][val] % mod; //zk = 1ll * zk * re_2[k] % mod; zk = 1ll * zk * gt[2 * k] % mod; zk = 1ll * zk * C[k][n - j + k] % mod; add(dp[i][j], zk); } //cout << dp[i][j] << ' '; } //cout << endl; } int ans = 0; for (int i = 0; i <= n; ++ i){ int val = 1ll * dp[m][i] * gt[(n - i) * 2] % mod; //val = 1ll * val * re_2[n - i] % mod; if (i % 2 == 0) add(ans, val); else add(ans, -val); } cout << ans; } int main(){ //freopen("code.inp", "r", stdin); //freopen("code.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; while (t --) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...