Submission #1000839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000839		Sharky	Tents (JOI18_tents)	C++17	100 / 100	118 ms	70992 KiB

tents

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int mod = 1000000007;

int fac[6001], ifac[6001], pw[6001], invpw[6001], dp[3001][3001];

int bm(int b, int p) {
    if (!p) return 1;
    int res = bm(b, p / 2);
    res = res * res % mod;
    if (p % 2 == 1) res = res * b % mod;
    return res;
}

int ncr(int n, int r) {
    return fac[n] * ifac[r] % mod * ifac[n - r] % mod;
}

int npr(int n, int r) {
    return fac[n] * ifac[n - r] % mod;
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int h, w, ans = 0;
    cin >> h >> w;
    fac[0] = ifac[0] = pw[0] = invpw[0] = 1;
    for (int i = 1; i <= 6000; i++) {
        fac[i] = fac[i - 1] * i % mod;
        ifac[i] = bm(fac[i], mod - 2);
        pw[i] = pw[i - 1] * 2 % mod;
        invpw[i] = bm(pw[i], mod - 2);
    }
    for (int i = 0; i <= max(h, w); i++) dp[i][0] = 1;
    for (int i = 0; i <= max(h, w); i++) {
        for (int j = 0; j <= max(h, w); j++) {
            if (j) dp[i][j] += dp[i][j - 1];
            if (i && j) dp[i][j] += dp[i - 1][j - 1] * 4 % mod * i % mod;
            dp[i][j] %= mod;
        }
    }
    for (int i = 0; i <= h; i++) { // number of horiz
        for (int j = 0; j <= w; j++) { // number of vert
            if (i + 2 * j > h || i * 2 + j > w) continue;
            int mn = min(h - (i + 2 * j), w - (i * 2 + j));
            int mx = max(h - (i + 2 * j), w - (i * 2 + j));
            ans += ncr(h, i) * ncr(w, j) % mod * npr(h - i, j * 2) % mod * npr(w - j, i * 2) % mod * invpw[j] % mod * invpw[i] % mod * dp[mn][mx] % mod;
            if (!i && !j) ans--;
            ans = (ans + mod) % mod;
            // cout << i << ' ' << j << '\n';
            // cout << ncr(h, i) << ' ' << ncr(w, j) << ' ' << npr(h - i, j * 2) * invpw[j] % mod << ' ' << npr(w - j, i * 2) * invpw[i] % mod << ' ' << dp[mx][mn] << '\n';
            // cout << ans << '\n';
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52