oj.uz

Submission #478313

# Submission time Handle Problem Language Result Execution time Memory
478313 2021-10-07T02:14:48 Z tranxuanbach Tents (JOI18_tents) C++17
100 / 100
 112 ms 35512 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 3e3 + 5, mod = 1e9 + 7;

inline void sadd(int& x, int y){
    if ((x += y) >= mod) x -= mod;
    return;
}

inline int add(int x, int y){
    if ((x += y) >= mod) x -= mod;
    return x;
}

inline void ssub(int& x, int y){
    if ((x -= y) < 0) x += mod;
    return;
}

inline int sub(int x, int y){
    if ((x -= y) < 0) x += mod;
    return x;
}

inline int mul(int x, int y){
    return 1ll * x * y % mod;
}

inline int binpow(int x, int y){
    int ans = 1;
    while (y){
        if (y & 1) ans = mul(ans, x);
        x = mul(x, x);
        y >>= 1;
    }
    return ans;
}

inline int inv(int x){
    return binpow(x, mod - 2);
}

#define div __div__
inline int div(int x, int y){
    return mul(x, binpow(y, mod - 2));
}

int fac[N], invfac[N];

void calfac(){
    fac[0] = invfac[0] = 1;
    For(i, 1, N){
        fac[i] = mul(fac[i - 1], i);
    }
    invfac[N - 1] = binpow(fac[N - 1], mod - 2);
    FordE(i, N - 2, 1){
        invfac[i] = mul(invfac[i + 1], i + 1);
    }
}

inline int C(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], mul(invfac[k], invfac[n - k]));
}

inline int P(int n, int k){
    if (n < 0 or k < 0 or k > n){
        return 0;
    }
    return mul(fac[n], invfac[n - k]);
}

int n, m;

int dp[N][N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    calfac();
    cin >> n >> m;
    ForE(j, 0, m){
        dp[0][j] = 1;
    }
    ForE(i, 1, n){
        ForE(j, 0, m){
            dp[i][j] = dp[i - 1][j];
            if (j >= 1){
                sadd(dp[i][j], mul(dp[i - 1][j - 1], 4 * j));
            }
            if (j >= 2){
                sadd(dp[i][j], mul(dp[i - 1][j - 2], j * (j - 1) / 2));
            }
            if (i >= 2 and j >= 1){
                sadd(dp[i][j], mul(dp[i - 2][j - 1], (i - 1) * j));
            }
        }
    }
    cout << sub(dp[n][m], 1) << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 1360 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 1616 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 1872 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 1 ms 1104 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 1360 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 1616 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 2 ms 1872 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 5 ms 9560 KB Output is correct
15 Correct 78 ms 32852 KB Output is correct
16 Correct 5 ms 2640 KB Output is correct
17 Correct 16 ms 7888 KB Output is correct
18 Correct 20 ms 10960 KB Output is correct
19 Correct 81 ms 34536 KB Output is correct
20 Correct 68 ms 29100 KB Output is correct
21 Correct 45 ms 19760 KB Output is correct
22 Correct 44 ms 22184 KB Output is correct
23 Correct 28 ms 19664 KB Output is correct
24 Correct 112 ms 35512 KB Output is correct
25 Correct 82 ms 30712 KB Output is correct
26 Correct 92 ms 33432 KB Output is correct
27 Correct 107 ms 34696 KB Output is correct