oj.uz

Submission #157115

# Submission time Handle Problem Language Result Execution time Memory
157115 2019-10-09T16:08:00 Z fedoseevtimofey Tents (JOI18_tents) C++14
100 / 100
 428 ms 71160 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 35832 KB Output is correct
2 Correct 81 ms 35704 KB Output is correct
3 Correct 80 ms 35704 KB Output is correct
4 Correct 78 ms 35680 KB Output is correct
5 Correct 86 ms 35832 KB Output is correct
6 Correct 81 ms 35820 KB Output is correct
7 Correct 82 ms 35824 KB Output is correct
8 Correct 80 ms 35836 KB Output is correct
9 Correct 81 ms 35780 KB Output is correct
10 Correct 81 ms 35916 KB Output is correct
11 Correct 80 ms 35800 KB Output is correct
12 Correct 84 ms 36168 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 35832 KB Output is correct
2 Correct 81 ms 35704 KB Output is correct
3 Correct 80 ms 35704 KB Output is correct
4 Correct 78 ms 35680 KB Output is correct
5 Correct 86 ms 35832 KB Output is correct
6 Correct 81 ms 35820 KB Output is correct
7 Correct 82 ms 35824 KB Output is correct
8 Correct 80 ms 35836 KB Output is correct
9 Correct 81 ms 35780 KB Output is correct
10 Correct 81 ms 35916 KB Output is correct
11 Correct 80 ms 35800 KB Output is correct
12 Correct 84 ms 36168 KB Output is correct
13 Correct 80 ms 35756 KB Output is correct
14 Correct 81 ms 35824 KB Output is correct
15 Correct 269 ms 57812 KB Output is correct
16 Correct 92 ms 37112 KB Output is correct
17 Correct 119 ms 40696 KB Output is correct
18 Correct 128 ms 41976 KB Output is correct
19 Correct 326 ms 61332 KB Output is correct
20 Correct 264 ms 56320 KB Output is correct
21 Correct 198 ms 49400 KB Output is correct
22 Correct 188 ms 49136 KB Output is correct
23 Correct 132 ms 43244 KB Output is correct
24 Correct 428 ms 71160 KB Output is correct
25 Correct 325 ms 61944 KB Output is correct
26 Correct 367 ms 65784 KB Output is correct
27 Correct 408 ms 69880 KB Output is correct