Submission #56990

#	Time	Username	Problem	Language	Result	Execution time	Memory
56990		choikiwon	마스코트 (JOI13_mascots)	C++17	100 / 100	264 ms	40844 KiB

mascots

#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int MN = 100010;
const int MX = 3010;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[MN], invf[MN];
int comb(int n, int k) {
    if(n < k) return 0;
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}

int R, C, N;
int mn1, mn2, mx1, mx2;

int cc[MX][MX];
int dp(int r, int c) {
    int &ret = cc[r][c];
    if(ret != -1) return ret;
    if(r == R && c == C) return ret = 1;

    ret = 0;
    if(r < R) {
        ret += 1LL * dp(r + 1, c) * fact[c] % mod;
        ret %= mod;
    }
    if(c < C) {
        ret += 1LL * dp(r, c + 1) * fact[r] % mod;
        ret %= mod;
    }
    return ret;
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < MN; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < MN; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d %d %d", &R, &C, &N);

    mn1 = mn2 = 1e9;
    mx1 = mx2 = -1e9;
    for(int i = 0; i < N; i++) {
        int r, c; scanf("%d %d", &r, &c);
        mn1 = min(mn1, r);
        mx1 = max(mx1, r);
        mn2 = min(mn2, c);
        mx2 = max(mx2, c);
    }

    int r = mx1 - mn1 + 1;
    int c = mx2 - mn2 + 1;

    memset(cc, -1, sizeof(cc));
    int ans = 1;
    for(int i = 1; i <= r * c - N; i++) ans = 1LL * ans * i % mod;
    ans = 1LL * ans * dp(r, c) % mod;
    ans = 1LL * ans * comb(R - r, mn1 - 1) % mod;
    ans = 1LL * ans * comb(C - c, mn2 - 1) % mod;
    printf("%d", ans);
}

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &R, &C, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int r, c; scanf("%d %d", &r, &c);
                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60