Submission #47519

#TimeUsernameProblemLanguageResultExecution timeMemory
47519qoo2p5Tents (JOI18_tents)C++17
48 / 100
2060 ms700 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = (int) 1e9 + 1e6 + 123; const ll LINF = (ll) 1e18 + 1e9 + 123; #define rep(i, s, t) for (auto i = (s); i < (t); ++(i)) #define per(i, s, t) for (auto i = (s); i >= (t); --(i)) #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define mp make_pair #define pb push_back bool mini(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } bool maxi(auto &x, const auto &y) { if (y > x) { x = y; return 1; } return 0; } void run(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); run(); return 0; } const ll MOD = (ll) 1e9 + 7; ll power(ll x, ll y) { if (y == 0) { return 1; } if (y % 2 == 0) { ll t = power(x, y / 2); return t * t % MOD; } else { return power(x, y - 1) * x % MOD; } } const int N = 3003; int H, W; ll f[N]; ll fact[N], rfact[N]; ll cnk(int n, int k) { return fact[n] * rfact[n - k] % MOD * rfact[k] % MOD; } ll calc2(int w, int h) { if ((w + h) % 3 != 0) { return 0; } int x = w - (w + h) / 3; int y = (w + h) / 3 - x; if (x < 0 || y < 0) { return 0; } ll res = cnk(w, y) * cnk(h, x) % MOD; res = res * f[x] % MOD; res = res * f[y] % MOD; return res; } ll calc1(int w, int h) { if (w < h) { swap(w, h); } ll res = 1; rep(cnt, 1, h + 1) { res = (res + cnk(w, cnt) * cnk(h, cnt) % MOD * fact[cnt] % MOD * power(4, cnt) % MOD) % MOD; } return res; } void run() { f[0] = 1; rep(i, 1, N) { f[i] = i * 1LL * (2 * i - 1) * f[i - 1] % MOD; } fact[0] = 1; rep(i, 1, N) { fact[i] = fact[i - 1] * i % MOD; } rep(i, 0, N) { rfact[i] = power(fact[i], MOD - 2); } ll ans = MOD - 1; cin >> H >> W; rep(h, 0, H + 1) { rep(w, 0, W + 1) { ll cur = calc2(w, h) * calc1(W - w, H - h) % MOD; cur = cur * cnk(W, w) % MOD; cur = cur * cnk(H, h) % MOD; ans = (ans + cur) % MOD; } } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...