Submission #317942

#	Time	Username	Problem	Language	Result	Execution time	Memory
317942		jainbot27	Tents (JOI18_tents)	C++17	100 / 100	1780 ms	36088 KiB

tents

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()

#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;

template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const char nl = '\n';
const int mxN = 3e3 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;

int fact[mxN*2];
int add(int x, int y){ x += y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void ad(int &x, int y) {x = add(x, y);}
int sub(int x, int y){ x -= y; while(x >= MOD) x -= MOD; while(x < 0) x += MOD; return x; } void sb(int &x, int y) {x = sub(x, y);}
int mul(int x, int y){ return ((int64_t)x * (int64_t)y) % MOD; } void ml(int &x, int y) {x = mul(x, y);}
int binpow(int x, int y){ int z = 1; while(y > 0) { if(y % 2 == 1) z = mul(z, x); x = mul(x, x); y /= 2; } return z; }
int inv(int x){ return binpow(x, MOD - 2); }
int divide(int x, int y){ return mul(x, inv(y)); }
void precalc(){ fact[0] = 1; for(int i = 1; i < 2*mxN; i++) fact[i] = mul(i, fact[i - 1]); }
int choose(int n, int k){ if(k > n) return 0; return divide(fact[n], mul(fact[n - k], fact[k])); }

int n, m, ans = 0, dp[mxN][mxN];

int c2(int x){
    return mul(x, mul(sub(x,1), inv(2)));
}

int d(int h, int v){
    if(dp[h][v]!=-1) return dp[h][v];
    if(h <= 0 || v <= 0) return 1;
    int res = 0;
    ad(res, d(h-1, v));
    ad(res, mul(4*v, d(h-1, v-1)));
    ad(res, mul(c2(v), d(h-1, v-2)));
    ad(res, mul(v, mul(h-1, d(h-2, v-1))));
    return dp[h][v] = res;
};
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> n >> m;
    cout << sub(d(n, m), 1) << nl;
}

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