Submission #157115

#	Time	Username	Problem	Language	Result	Execution time	Memory
157115		fedoseevtimofey	Tents (JOI18_tents)	C++14	100 / 100	428 ms	71160 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int md = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if (a >= md) a -= md;
    if (a < 0) a += md;
}

int mul(int a, int b) {
    return ((ll)a * b) % md;
}

int power(int a, ll b) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = mul(res, a);
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int a) {
    return power(a, md - 2);
}

const int N = 3007;

int C[N][N];
int f[N], rf[N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    f[0] = 1;
    for (int i = 1; i < N; ++i) f[i] = mul(f[i - 1], i);
    for (int i = 0; i < N; ++i) rf[i] = inv(f[i]);
    int n, m;
    cin >> n >> m;
    vector <vector <int>> dp(n + 1, vector <int> (m + 1));
    C[0][0] = 1;
    for (int n = 1; n < N; ++n) {
        C[n][0] = 1;
        for (int k = 1; k < N; ++k) {
            add(C[n][k], C[n - 1][k]);
            add(C[n][k], C[n - 1][k - 1]);
        }
    }
    for (int i = 0; i <= n; ++i) dp[i][0] = 1;
    for (int j = 0; j <= m; ++j) dp[0][j] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            add(dp[i][j], dp[i - 1][j]);
            if (j >= 2) add(dp[i][j], mul(C[j][2], dp[i - 1][j - 2]));
            if (i >= 2) add(dp[i][j], mul(j, mul(i - 1, dp[i - 2][j - 1])));
        }
    }
    int ans = 0;
    int st = 1;
    int cur = 1;
    for (int cnt = 0; cnt <= min(n, m); ++cnt) {
        add(ans, mul(mul(cur, mul(st, dp[n - cnt][m - cnt])), rf[cnt]));
        st = mul(st, 4);
        cur = mul(cur, n - cnt);
        cur = mul(cur, m - cnt);
    }
    add(ans, -1);
    cout << ans << '\n';
}

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