oj.uz

Submission #1000839

# Submission time Handle Problem Language Result Execution time Memory
1000839 2024-06-18T09:59:42 Z Sharky Tents (JOI18_tents) C++17
100 / 100
 118 ms 70992 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 4 ms 6744 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Correct 4 ms 8796 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 4 ms 6744 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 4 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6748 KB Output is correct
8 Correct 3 ms 6748 KB Output is correct
9 Correct 3 ms 4700 KB Output is correct
10 Correct 4 ms 8796 KB Output is correct
11 Correct 4 ms 8796 KB Output is correct
12 Correct 5 ms 8796 KB Output is correct
13 Correct 29 ms 40668 KB Output is correct
14 Correct 55 ms 53072 KB Output is correct
15 Correct 88 ms 65364 KB Output is correct
16 Correct 20 ms 34136 KB Output is correct
17 Correct 29 ms 38748 KB Output is correct
18 Correct 23 ms 30044 KB Output is correct
19 Correct 96 ms 68932 KB Output is correct
20 Correct 70 ms 57680 KB Output is correct
21 Correct 49 ms 46164 KB Output is correct
22 Correct 60 ms 49016 KB Output is correct
23 Correct 68 ms 70992 KB Output is correct
24 Correct 118 ms 70952 KB Output is correct
25 Correct 88 ms 61256 KB Output is correct
26 Correct 96 ms 66640 KB Output is correct
27 Correct 105 ms 70224 KB Output is correct