Submission #871121

#TimeUsernameProblemLanguageResultExecution timeMemory
871121MinaRagy06NoM (RMI21_nom)C++17
100 / 100
211 ms63608 KiB
#include <bits/stdc++.h> using namespace std; typedef int64_t ll; const int mod = 1e9 + 7; struct mint { int v; mint(long long x) { if (x >= mod) x %= mod; v = x; } mint() {v = 0;} mint& operator+=(mint b) { if ((v += b.v) >= mod) { v -= mod; } return *this; } mint& operator-=(mint b) { if ((v -= b.v) < 0) { v += mod; } return *this; } mint& operator*=(mint b) { v = 1ll * v * b.v % mod; return *this; } mint power(mint a, int b) { mint ans = 1; while (b) { if (b & 1) { ans *= a; } a *= a, b >>= 1; } return ans; } mint& operator/=(mint b) { v = 1ll * v * power(b, mod - 2).v % mod; return *this; } friend mint operator+(mint a, mint b) { return a += b; } friend mint operator-(mint a, mint b) { return a -= b; } friend mint operator*(mint a, mint b) { return a *= b; } friend mint operator/(mint a, mint b) { return a /= b; } friend istream& operator>>(istream &is, mint a) { return is >> a.v; } friend ostream& operator<<(ostream &os, mint a) { return os << a.v; } }; const int N = 4005; mint dp[N][N], fact[N], inv[N]; mint nCr(int n, int r) { return fact[n] * inv[n - r] * inv[r]; } mint nPr(int n, int r) { return fact[n] * inv[n - r]; } int main() { ios_base::sync_with_stdio(0), cin.tie(0); fact[0] = 1; for (int i = 1; i < N; i++) { fact[i] = fact[i - 1] * i; } inv[N - 1] = 1 / fact[N - 1]; for (int i = N - 2; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1); } int n, m; cin >> n >> m; int a[m]{}; for (int i = 0; i < 2 * n; i++) { a[i % m]++; } dp[m][0] = 1; for (int i = m - 1; i >= 0; i--) { for (int j = 0; j <= 2 * n; j++) { for (int k = 0; k <= min(j, a[i]); k++) { dp[i][j] += dp[i + 1][a[i] - k + j - k] * nPr(a[i], k) * nCr(j, k); } } } cout << dp[0][0] * fact[n] * mint().power(2, n) << '\n'; 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...