oj.uz

Submission #676313

# Submission time Handle Problem Language Result Execution time Memory
676313 2022-12-30T09:26:07 Z tengiz05 Tents (JOI18_tents) C++17
100 / 100
 285 ms 35776 KB 
// solutions need to be proved and have general ideas

#include <bits/stdc++.h>

constexpr int P = 1E9 + 7;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, int b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(i64 x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
};

constexpr int N = 10000;
Z fac[N + 1], inv[N + 1];
Z nCk(int n, int k) {
    if (n < k) {
        return 0;
    }
    return fac[n] * inv[k] * inv[n - k];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= N; i++) {
        fac[i] = fac[i - 1] * i;
        inv[i] = 1 / fac[i];
    }
    
    int h, w;
    std::cin >> h >> w;
    
    std::vector dp(h + 3, std::vector<Z>(w + 3));
    
    for (int i = 0; i <= w; i++) {
        dp[0][i] = 1;
    }
    
    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            dp[i + 1][j] += dp[i][j];
            dp[i + 1][j + 1] += nCk(j + 1, 1) * 4 * dp[i][j];
            dp[i + 1][j + 2] += nCk(j + 2, 2) * dp[i][j];
            dp[i + 2][j + 1] += nCk(i + 1, 1) * nCk(j + 1, 1) * dp[i][j];
        }
    }
    
    std::cout << (dp[h][w] - 1).val() << "\n";
    
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 5 ms 724 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 400 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 5 ms 724 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 524 KB Output is correct
15 Correct 178 ms 22428 KB Output is correct
16 Correct 13 ms 1748 KB Output is correct
17 Correct 42 ms 5332 KB Output is correct
18 Correct 62 ms 6516 KB Output is correct
19 Correct 210 ms 26044 KB Output is correct
20 Correct 162 ms 20924 KB Output is correct
21 Correct 109 ms 13932 KB Output is correct
22 Correct 112 ms 13652 KB Output is correct
23 Correct 59 ms 7892 KB Output is correct
24 Correct 285 ms 35776 KB Output is correct
25 Correct 224 ms 26644 KB Output is correct
26 Correct 236 ms 30420 KB Output is correct
27 Correct 268 ms 34536 KB Output is correct