Submission #37469

#	Time	Username	Problem	Language	Result	Execution time	Memory
37469		nickyrio	마스코트 (JOI13_mascots)	C++14	100 / 100	356 ms	186660 KiB

mascots

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 3333
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
#define bit(S, i) (((S) >> i) & 1)
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

int q, n, m, a[N][N];
const int MOD = 1e9 + 7;
int gt[N * N], dp[N][N], c[N][N];
bool used[N][N];

int cal(int r, int c) {
    if (r == m && c == n) return 1;
    if (used[r][c]) return dp[r][c];
    used[r][c] = true;
    dp[r][c] = 0;
    if (r != m) {
        dp[r][c] = (dp[r][c] + 1ll * cal(r + 1, c) * gt[c] % MOD) % MOD;
    }
    if (c != n) {
        dp[r][c] = (dp[r][c] + 1ll * cal(r, c + 1) * gt[r] % MOD) % MOD;
    }
    return dp[r][c];
}

void init() {
    FOR(i, 0, max(m, n)) c[0][i] = 1;
    FOR(i, 1, max(m, n)) {
        c[i][i] = 1;
        FOR(j, i + 1, max(m, n)) {
            c[i][j] = (c[i][j - 1] + c[i - 1][j - 1]) % MOD;
        }
    }
}
int main() {
    IO;
    //freopen("LANDS.inp","r",stdin);
    //freopen("LANDS.out","w",stdout);
    read(m);read(n);
    gt[0] = 1;
    FOR(i, 1, m * n) gt[i] = 1ll * gt[i - 1] * i % MOD;
    read(q);
    int mnx = 1e9, mny = 1e9, mxx = -1e9, mxy = -1e9;
    int u, v;
    while (q--) {
        read(u);read(v);
        a[u][v] = 1;
        mnx = min(u, mnx);
        mxx = max(u, mxx);
        mny = min(v, mny);
        mxy = max(v, mxy);
    }
    if (n == 0) {
        writeln(gt[n * m]);
        return 0;
    }
    init();
    int total = cal(mxx - mnx + 1, mxy - mny + 1);
    FOR(i, 1, m) FOR(j, 1, n) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    int cnt = a[mxx][mxy] - a[mxx][mny - 1] - a[mnx - 1][mxy] + a[mnx - 1][mny - 1];
    total = 1ll * total * gt[(mxx - mnx + 1) * (mxy - mny + 1) - cnt] % MOD;
    total = (1ll * total * c[mnx - 1][m - (mxx - mnx + 1)]) % MOD;
    total = (1ll * total * c[mny - 1][n - (mxy - mny + 1)]) % MOD;
    writeln(total);
}

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