Submission #897729

#TimeUsernameProblemLanguageResultExecution timeMemory
897729denniskimNoM (RMI21_nom)C++17
52 / 100
142 ms31704 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2") using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n, m; ll ss = 1000000007; ll ans; ll cou[2010]; ll dp[4000010]; ll fac[5010] = {0, }, inv[5010] = {0, }; ll num(ll X, ll Y) { return X * (m + 1) + Y; } ll power(ll xx, ll yy) { ll ret = 1; while(yy > 0) { if(yy % 2) ret = (ret * xx) % ss; xx = (xx * xx) % ss; yy /= 2; } return ret; } ll C(ll xx, ll yy) { if(xx < yy) return 0; if(xx == yy || !yy) return 1; long long r = (fac[xx] * inv[xx - yy]) % ss; r = (r * inv[yy]) % ss; return r; } void init(void) { fac[0] = 1; fac[1] = 1; for(ll i = 2 ; i <= 4500 ; i++) fac[i] = (fac[i - 1] * i) % ss; inv[4500] = power(fac[4500], ss - 2); for(ll i = 4499 ; i >= 0 ; i--) inv[i] = (inv[i + 1] * (i + 1)) % ss; } int main(void) { fastio cin >> n >> m; init(); ll siz = n * 2; ans = fac[siz]; for(ll i = 1 ; i <= siz ; ++i) { ll gap = i % m; if(gap == 0) gap = m; cou[gap]++; } for(ll i = 0 ; i <= m ; ++i) dp[num(0, i)] = 1; for(ll i = 1 ; i <= n ; ++i) { for(ll j = 1 ; j <= m ; ++j) { ll X = cou[j]; for(ll k = 1 ; k * 2 <= X && k <= i ; ++k) { dp[num(i, j)] = (dp[num(i, j)] + dp[num(i - k, j - 1)] * C(X, k * 2) % ss * fac[k * 2] % ss * C(i, k) % ss); if(dp[num(i, j)] < 0) dp[num(i, j)] += ss; else if(dp[num(i, j)] > ss) dp[num(i, j)] -= ss; } } for(ll j = 1 ; j <= m ; ++j) { dp[num(i, j)] = (dp[num(i, j)] + dp[num(i, j - 1)]); if(dp[num(i, j)] < 0) dp[num(i, j)] += ss; else if(dp[num(i, j)] > ss) dp[num(i, j)] -= ss; } } for(ll i = 1 ; i <= n ; ++i) { ll gap = dp[num(i, m)] * C(n, i) % ss * fac[n * 2 - i * 2] % ss; if(i & 1) { ans = (ans - gap); if(ans < 0) ans += ss; else if(ans > ss) ans -= ss; } else { ans = (ans + gap); if(ans < 0) ans += ss; else if(ans > ss) ans -= ss; } } ans = (ans + ss) % ss; cout << ans; 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...