Submission #529026

#TimeUsernameProblemLanguageResultExecution timeMemory
529026fhvirusTents (JOI18_tents)C++17
48 / 100
2088 ms24052 KiB
#include <bits/stdc++.h> using namespace std; typedef int64_t ll; typedef pair<int, int> pii; #define pb emplace_back #define AI(x) begin(x),end(x) #define ff first #define ss second #ifdef OWO #define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args) template <class I> void LKJ(I&&x) { cerr << x << endl; } template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); } template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; } #else #define debug(...) 0 #define OI(...) 0 #endif const int MOD = 1'000'000'007; int mad(int u, int v) { u += v - MOD; u += MOD & (u >> 31); return u; } int mul(int u, int v) { return (ll) u * v % MOD; } int mow(int x, int e) { int r = 1; while (e) { if (e & 1) r = mul(r, x); x = mul(x, x); e >>= 1; } return r; } const int kN = 3003; int fac[kN], caf[kN], inv[kN]; void init(int n) { fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i); caf[n] = mow(fac[n], MOD - 2); for (int i = n; i >= 1; --i) caf[i - 1] = mul(caf[i], i); for (int i = 1; i <= n; ++i) inv[i] = mul(fac[i - 1], caf[i]); } int C(int n, int k) { if (0 > k or k > n) return 0; return mul(fac[n], mul(caf[k], caf[n - k])); } int P(int n, int k) { if (0 > k or k > n) return 0; return mul(fac[n], caf[n - k]); } int H, W, ans; int tmp[kN][kN]; int solve(int n, int m) { if (n > m) swap(n, m); if (tmp[n][m] != -1) return tmp[n][m]; tmp[n][m] = 0; for (int i = 0; i <= n; ++i) tmp[n][m] = mad(tmp[n][m], mul(mul(C(n, i), P(m, i)), mow(4, i))); return tmp[n][m]; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> H >> W; if (H > W) swap(H, W); init(max(H, W)); for (int i = 0; i <= H; ++i) for (int j = 0; j <= W; ++j) tmp[i][j] = -1; for (int r = 0; r <= H and 2 * r <= W; ++r) for (int c = 0; r + 2 * c <= H and 2 * r + c <= W; ++c) { int v = mul(C(H, r), mul(P(W, 2 * r), mow(inv[2], r))); v = mul(v, mul(C(W - 2 * r, c), mul(P(H - r, 2 * c), mow(inv[2], c)))); v = mul(v, solve(H - (r + 2 * c), W - (2 * r + c))); ans = mad(ans, v); } cout << mad(ans, MOD - 1) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...