Submission #509532

#TimeUsernameProblemLanguageResultExecution timeMemory
509532hohohahaNoM (RMI21_nom)C++14
9 / 100
1 ms560 KiB
// #pragma GCC optimize("Ofast") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") // #pragma GCC optimize("unroll-loops") #include "bits/stdc++.h" // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/trie_policy.hpp> // #include <ext/rope> using namespace std; // using namespace __gnu_pbds; // using namespace __gnu_cxx; #define li long long #define ld long double #define ii pair<int, int> #define vi vector<int> #define vvi vector<vi> #define fi first #define se second #define mp make_pair #define pb push_back #define pf push_front #define eb emplace_back #define em emplace #define ob pop_back #define om pop #define of pop_front #define fr front #define bc back #define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i) #define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i) #define all(x) begin(x), end(x) #define sz(x) ((int)(x).size()) #define bitc __builtin_popcountll mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rand rng #define endl '\n' #define sp ' ' #define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define forIT(it, begin, end) for(__typeof(end) it = (begin) - ((begin) > (end)); it != (end) - ((begin) > (end)); it += 1 - 2 * ((begin) > (end)) ) void solve(); signed main() { // freopen("test.inp", "r", stdin); // fastio(); int tc = 1; // cin >> tc; fori(test, 1, tc) { solve(); } return 0; } #define int long long const ld pi = 4 * atan(1.0), eps = 1e-9; const int maxn = 4000 + 5, inf = LLONG_MAX / 100ll, mod = 1e9 + 7; int n, m; int fac[maxn]; int inv_fac[maxn]; int bp(int i, int p) { int r = 1; while(p) { if(p & 1) r = r * i % mod; i = i * i % mod; p >>= 1; } return r; } int C(int n, int k) { if(k < 0 or k > n) return 0; return fac[n] * inv_fac[n - k] % mod * inv_fac[k] % mod; } int dp[maxn][maxn]; int w[maxn]; void solve() { cin >> n >> m; fac[0] = inv_fac[0] = 1; fori(i,1,2 * n) { fac[i] = fac[i - 1] * i % mod; inv_fac[i] = bp(fac[i], mod -2); } fori(i, 0, m - 1) { int num = 2 * n / m + (i < 2 * n % m); // cout << i << sp << num << sp << endl; fori(used, 0, n) { fori(tran, 0, num / 2) { (dp[i][used + tran] += (i? dp[i - 1][used]: used == 0) * C(tran + used, tran) % mod * fac[num] % mod * inv_fac[num - 2 * tran] % mod) %= mod; } } // fori(used, 0, n) { // cout << i << sp << used << sp << dp[i][used] << endl; // } } // cout << C(2, 1) << endl; int ans = 0; fori(i, 0, n) { w[i] = dp[m - 1][i] * fac[2 * n - 2 * i] % mod; //cout << i << sp << w[i] << endl; (ans += w[i] * C(n, i) * bp(-1, i) % mod) %= mod; } cout << ans; }
#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...