제출 #892701

#제출 시각아이디문제언어결과실행 시간메모리
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...