Submission #364644

#	Time	Username	Problem	Language	Result	Execution time	Memory
364644		parsabahrami	Tents (JOI18_tents)	C++17	100 / 100	252 ms	63340 KiB

tents

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

int Pow(int a, int b, int md, int ret = 1) {
    for (; b; b >>= 1, a = 1ll * a * a % md) {
        if (b & 1) ret = 1ll * ret * a % md;
    }
    return ret;
}

const int N = 3e3 + 10, MOD = 1e9 + 7;
int dp[N][N], pd[N][N], F[N], I[N], w, h;

int C(int x, int y) {
    if (y < 0 || x < y) return 0;
    return 1ll * F[x] * I[y] % MOD * I[x - y] % MOD;
}

int main() {
    scanf("%d%d", &w, &h);
    F[0] = 1;
    for (int i = 1; i < N; i++) F[i] = 1ll * F[i - 1] * i % MOD;
    I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
    for (int i = N - 1; i; i--) {
        I[i - 1] = I[i] * 1ll * i % MOD;
    }
    pd[0][0] = 1;
    for (int i = 0; i < max(w, h); i++) {
        for (int j = 0; j <= i; j++) {
            pd[i + 1][j + 1] = (pd[i + 1][j + 1] + pd[i][j]) % MOD;
            if (j) pd[i + 1][j - 1] = (pd[i + 1][j - 1] + pd[i][j] * 1ll * j % MOD) % MOD;
        }
    }
    for (int i = 0; i <= max(w, h); i++) {
        for (int j = 0; j <= max(w, h); j++) {
            if (!i || !j) dp[i][j] = 1;
            else dp[i][j] = (dp[i - 1][j] + 1ll * dp[i - 1][j - 1] * 4 * j % MOD) % MOD;
        }
    }
    int ret = 0;
    for (int c1 = 0; c1 <= max(w, h); c1++) {
        for (int c2 = 0; c2 <= max(w, h); c2++) {
            if (w - 2 * c1 - c2 >= 0 && h - 2 * c2 - c1 >= 0) {
                int x = C(w, 2 * c1) * 1ll * C(w - 2 * c1, c2) % MOD;
                x = 1ll * x * pd[2 * c1][0] % MOD;
                int y = C(h, 2 * c2) * 1ll * C(h - 2 * c2, c1) % MOD;
                y = 1ll * y * pd[2 * c2][0] % MOD;
                int nw = 1ll * x * y % MOD * F[c1] % MOD * F[c2] % MOD * dp[w - 2 * c1 - c2][h - 2 * c2 - c1] % MOD;
                ret = (ret + nw) % MOD;
            }
        }
    }
    printf("%d\n", ret - 1);
    return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%d%d", &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~

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