oj.uz

Submission #768342

# Submission time Handle Problem Language Result Execution time Memory
768342 2023-06-28T00:07:38 Z raysh07 Tents (JOI18_tents) C++17
100 / 100
 157 ms 72396 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int facN = 1e5 + 1;
const long long mod = 1e9 + 7;
long long fac[facN], invfac[facN];

long long power(int x, int y){
    if (y==0) return 1;
    
    long long v = power(x, y/2);
    v *= v; v%= mod;
    
    if (y&1) return v * x % mod;
    else return v;
}

void Factorials(bool inverse = true){
    fac[0] = invfac[0] = 1;
    for (int i=1; i<facN; i++){
        fac[i] = fac[i-1] * i % mod;
    }
    
    if (!inverse) return;
    
    invfac[facN - 1] = power(fac[facN - 1], mod - 2);
    for (int i=facN - 2; i>=0; i--){
        invfac[i] = invfac[i+1] * (i + 1) % mod;
    }
}

long long C(int n, int r){
    return fac[n] * invfac[r] % mod * invfac[n-r] % mod;
}

long long P(int n, int r){
    return fac[n] * invfac[n-r] % mod;
}

long long Solutions(int n, int r){
    //x1 + .... + xn = r non negative integer solutions 
    return C(n + r - 1, n - 1);
}

long long inverse(int n){
    return power(n, mod - 2);
}

//remember to update facN and mod to the value you want 
//remember to actually call the Factorials function


void Solve() 
{
    Factorials();
    int h, w; cin >> h >> w;
    
    vector<vector<int>> dp(h + 1, vector<int>(w + 1, 0));
    for (int i = 0; i <= h; i++){
        for (int j = 0; j <= w; j++){
            if (i == 0 || j == 0){
                dp[i][j] = 1;
                continue;
            }
            
            //either there is thing in last row 
            dp[i][j] = 4 * j * dp[i - 1][j - 1] + dp[i - 1][j];
            dp[i][j] %= mod;
        }
    }
    
    int ans = 0;
    vector <int> dp1(max(h, w) + 1, 1);
    
    for (int i = 1; i <= max(h, w); i++){
        dp1[i] = dp1[i - 1] * C(2 * i, 2) % mod;
    }
    
    for (int i = 0; i <= h; i++){
        for (int j = 0; j <= w; j++){
            int l1 = h - i - 2 * j;
            int l2 = w - j - 2 * i;
            
            if (l1 < 0 || l2 < 0) continue;
            int ways = C(h, i) * C(w, j) % mod * C(h - i, 2 * j) % mod * C(w - j, 2 * i) % mod * dp1[i] % mod * dp1[j] % mod;
            ans += ways * dp[l1][l2] % mod;
            ans %= mod;
        }
    }
    if (ans == 0) ans += mod;
    cout << ans - 1 << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
   // cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 3 ms 2004 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 2 ms 2016 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 3 ms 2144 KB Output is correct
11 Correct 2 ms 1812 KB Output is correct
12 Correct 3 ms 2516 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 2 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 2004 KB Output is correct
6 Correct 3 ms 2004 KB Output is correct
7 Correct 3 ms 2004 KB Output is correct
8 Correct 2 ms 2016 KB Output is correct
9 Correct 2 ms 1876 KB Output is correct
10 Correct 3 ms 2144 KB Output is correct
11 Correct 2 ms 1812 KB Output is correct
12 Correct 3 ms 2516 KB Output is correct
13 Correct 2 ms 1876 KB Output is correct
14 Correct 3 ms 2024 KB Output is correct
15 Correct 96 ms 45796 KB Output is correct
16 Correct 5 ms 4620 KB Output is correct
17 Correct 13 ms 11604 KB Output is correct
18 Correct 20 ms 14036 KB Output is correct
19 Correct 112 ms 53060 KB Output is correct
20 Correct 82 ms 42776 KB Output is correct
21 Correct 41 ms 28756 KB Output is correct
22 Correct 48 ms 28372 KB Output is correct
23 Correct 17 ms 16696 KB Output is correct
24 Correct 157 ms 72396 KB Output is correct
25 Correct 110 ms 54232 KB Output is correct
26 Correct 134 ms 61952 KB Output is correct
27 Correct 154 ms 69732 KB Output is correct