Submission #1253650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253650		Bahamin	Tents (JOI18_tents)	C++20	100 / 100	158 ms	40376 KiB

tents

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;

const int h = MAX_N, w = MAX_N;
vector<ll> inv(h+w+1);
vector<ll> fact(h+w+1);
vector<ll> fact_inv(h+w+1);

inline int md(ll x) {x %= MOD; return x + (x < 0 ? MOD : 0);}
inline int ADD(ll a, ll b) { return md(a+b); }
inline int SUB(ll a, ll b) { return md(a-b); }
inline int MUL(ll a, ll b) { return md(1ll*a*b); }
inline int POW(ll a, ll b) { int res=1;while(b){if(b&1)res=MUL(res,a);a=MUL(a,a);b>>=1;}return res; }
inline int DIV(ll a, ll b) { return MUL(a, POW(b, MOD-2)); }

inline int comb(int n, int k){
    if (n<0 || k<0) return 0LL;
    if (n < k) return 0LL;
    return fact[n] * fact_inv[n - k] % MOD * fact_inv[k] % MOD;
};

void init()
{
    inv[1] = 1;
    for(int i=2; i<h+w+1; i++){
        inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
    }
    fact[0] = 1; 
    fact_inv[0] = 1; 
    for(int i=1; i<h+w+1; i++){
        fact[i] = fact[i-1] * i % MOD;
        fact_inv[i] = fact_inv[i-1] * inv[i] % MOD;
    }
}

void solve() {
    init();
    int h, w;
    cin >> h >> w;
    int dp[h + 1][w + 1];
    for (int i = 0; i <= w; i++) dp[0][i] = 1;
    for (int i = 0; i <= h; i++) dp[i][0] = 1;
    for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++)
        dp[i][j] = ADD(dp[i - 1][j], ADD(MUL(comb(j, 2), (j >= 2 ? dp[i - 1][j - 2] : 0)), ADD(MUL(MUL(j, 4), dp[i - 1][j - 1]), MUL(MUL(j, i - 1), (i >= 2 ? dp[i - 2][j - 1] : 0)))));
    cout << SUB(dp[h][w], 1) << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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