Submission #892711

#	Time	Username	Problem	Language	Result	Execution time	Memory
892711		box	Tents (JOI18_tents)	C++17	100 / 100	124 ms	89104 KiB

tents

#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 dp[N + 1][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;
    for (int i = 0; i <= N; i++) dp[i][0] = dp[0][i] = 1;
    for (int n = 1; n <= N; n++) for (int m = 1; m <= N; m++) {
        // fix what to do on the last row
        dp[n][m] += dp[n - 1][m]; // do nothing
        dp[n][m] += dp[n - 1][m - 1] * m * 4 % MOD; // single cell
        if (m >= 2) dp[n][m] += dp[n - 1][m - 2] * nck(m, 2) % MOD; // paired up, horizontal
        if (n >= 2) dp[n][m] += dp[n - 2][m - 1] * m * (n - 1) % MOD; // paired up, vertical
        dp[n][m] %= MOD;
    }
    cin >> h >> w;
    cout << dp[h][w] - 1 << '\n';
}

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