Submission #113084

#	Time	Username	Problem	Language	Result	Execution time	Memory
113084		popovicirobert	Tents (JOI18_tents)	C++14	100 / 100	133 ms	35832 KiB

tents

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const int MOD = (int) 1e9 + 7;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD) x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

vector <int> fact, invfact;

inline void prec(int n) {
    fact.resize(n + 1), invfact.resize(n + 1);

    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    for(int i = 0; i <= n; i++) {
        invfact[i] = lgput(fact[i], MOD - 2);
    }
}

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

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    prec(n + m);

    vector < vector <int> > dp(n + 1, vector <int>(m + 1));

    for(i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    for(i = 0; i <= m; i++) {
        dp[0][i] = 1;
    }

    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            dp[i][j] = dp[i - 1][j];
            dp[i][j] = (dp[i][j] + 4LL * j * dp[i - 1][j - 1]) % MOD;
            if(j >= 2) {
                dp[i][j] = (dp[i][j] + 1LL * comb(j, 2) * dp[i - 1][j - 2]) % MOD;
            }
            if(i >= 2) {
                dp[i][j] = (dp[i][j] + 1LL * j * (i - 1) * dp[i - 2][j - 1]) % MOD;
            }
        }
    }

    dp[n][m] += MOD - 1;
    mod(dp[n][m]);

    cout << dp[n][m];

    //cin.close();
    //cout.close();
    return 0;
}

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