Submission #892701

#TimeUsernameProblemLanguageResultExecution timeMemory
892701boxTents (JOI18_tents)C++17
48 / 100
2037 ms19116 KiB
#include <bits/stdc++.h> using namespace std; #define ar array #define sz(v) int(std::size(v)) using i64 = long long; const int N = 3000; const i64 MOD = 1e9 + 7; int h, w; int take[N + 1][N + 1]; i64 roll[N + 1]; i64 fac[N + 1], ifac[N + 1], p4[N + 1]; i64 inv(i64 a) { return a == 1 ? 1 : inv(MOD % a) * (MOD - MOD / a) % MOD; } i64 nck(int n, int k) { if (n < k || k < 0) return 0; return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); roll[1] = 1; for (int i = 3; i <= N; i += 2) roll[i] = roll[i - 2] * i % MOD; fac[0] = ifac[0] = 1; for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD, ifac[i] = inv(fac[i]); p4[0] = 1; for (int i = 1; i <= N; i++) p4[i] = p4[i - 1] * 4 % MOD; for (int k = 0; k <= N / 2; k++) for (int n = 0; n <= N; n++) take[k][n] = nck(n, k * 2) * (!k ? 1 : roll[k * 2 - 1]) % MOD; cin >> h >> w; i64 ans = 0; for (int x = 0; x <= w; x++) for (int y = 0; y <= h; y++) for (int z = 0; z <= min(w, h); z++) { i64 num = nck(w, x) * take[x][h] % MOD * nck(h - 2 * x, y) % MOD * take[y][w - x] % MOD * fac[x] % MOD * fac[y] % MOD * nck(w - x - 2 * y, z) % MOD * nck(h - 2 * x - y, z) % MOD * fac[z] % MOD * p4[z] % MOD; ans = (ans + num) % MOD; } ans += MOD - 1; ans %= MOD; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...