Submission #374883

#	Time	Username	Problem	Language	Result	Execution time	Memory
374883		ngpin04	마스코트 (JOI13_mascots)	C++14	100 / 100	381 ms	107884 KiB

mascots

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60