oj.uz

Submission #374883

# Submission time Handle Problem Language Result Execution time Memory
374883 2021-03-08T12:23:17 Z ngpin04 마스코트 (JOI13_mascots) C++14
100 / 100
 381 ms 107884 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 3e3 + 5;
const int mod = 1e9 + 7;

int fac[N * N];
int inv[N * N];
int dp[N][N];
int n,m,k;

int comb(int k, int n) {
    return (long long) fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int binpow(int n, int k) {
    int res = 1;
    for (; k; k >>= 1, n = (long long) n * n % mod)
        if (k & 1)
            res = (long long) res * n % mod;
    return res;
}

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

int solve(int i, int j) {
    int &res = dp[i][j];
    if (res != -1)
        return res;
    if (i == n && j == m)
        return 1;
    res = 0;

    if (i < n)
        add(res, (long long) solve(i + 1, j) * fac[j] % mod);
    if (j < m)
        add(res, (long long) solve(i, j + 1) * fac[i] % mod);
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);

    cin >> n >> m >> k;

    fac[0] = 1;
    for (int i = 1; i < N * N; i++)
        fac[i] = (long long) fac[i - 1] * i % mod;

    inv[N * N - 1] = binpow(fac[N * N - 1], mod - 2);
    for (int i = N * N - 2; i >= 0; i--)
        inv[i] = (long long) inv[i + 1] * (i + 1) % mod;

    int x = 1e9, y = 1e9;
    int u = 0, v = 0;
    for (int i = 1; i <= k; i++) {
        int a,b; cin >> a >> b;
        x = min(x, a);
        y = min(y, b);
        u = max(u, a);
        v = max(v, b);
    }

    int lenx = (u - x + 1);
    int leny = (v - y + 1);

    int ans = fac[lenx * leny - k];

    memset(dp, -1, sizeof(dp));

    ans = (long long) ans * solve(lenx, leny) % mod;

    x--;
    u = (n - u);

    y--;
    v = (m - v);

    ans = (long long) ans * comb(x, x + u) % mod * comb(y, y + v) % mod;

    cout << ans;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 106348 KB Output is correct
2 Correct 183 ms 106348 KB Output is correct
3 Correct 182 ms 106348 KB Output is correct
4 Correct 181 ms 106476 KB Output is correct
5 Correct 185 ms 106348 KB Output is correct
6 Correct 180 ms 106436 KB Output is correct
7 Correct 185 ms 106476 KB Output is correct
8 Correct 183 ms 106348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 106348 KB Output is correct
2 Correct 180 ms 106348 KB Output is correct
3 Correct 182 ms 106348 KB Output is correct
4 Correct 181 ms 106368 KB Output is correct
5 Correct 184 ms 106476 KB Output is correct
6 Correct 180 ms 106496 KB Output is correct
7 Correct 181 ms 106368 KB Output is correct
8 Correct 196 ms 106348 KB Output is correct
9 Correct 180 ms 106348 KB Output is correct
10 Correct 181 ms 106348 KB Output is correct
11 Correct 182 ms 106348 KB Output is correct
12 Correct 185 ms 106348 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 106476 KB Output is correct
2 Correct 181 ms 106348 KB Output is correct
3 Correct 182 ms 106508 KB Output is correct
4 Correct 200 ms 106476 KB Output is correct
5 Correct 198 ms 106476 KB Output is correct
6 Correct 206 ms 107244 KB Output is correct
7 Correct 186 ms 106476 KB Output is correct
8 Correct 181 ms 106604 KB Output is correct
9 Correct 194 ms 107200 KB Output is correct
10 Correct 367 ms 106732 KB Output is correct
11 Correct 298 ms 106604 KB Output is correct
12 Correct 192 ms 107052 KB Output is correct
13 Correct 183 ms 106348 KB Output is correct
14 Correct 180 ms 106476 KB Output is correct
15 Correct 381 ms 107628 KB Output is correct
16 Correct 325 ms 106604 KB Output is correct
17 Correct 199 ms 106988 KB Output is correct
18 Correct 372 ms 107884 KB Output is correct