Submission #35019

#	Time	Username	Problem	Language	Result	Execution time	Memory
35019		ztrong	마스코트 (JOI13_mascots)	C++14	100 / 100	173 ms	213816 KiB

mascots

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

#define llint long long

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #else
    //freopen("name.inp", "r", stdin);
    //freopen("name.out", "w", stdout);
    #endif
}

const int maxN = 3e3 + 5;
const int maxM = 1e6 + 5;
const llint INF = 1e9 + 7;

int N, R, C;
int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
llint dp[maxN][maxN], gt[maxN * maxN], cc[maxN][maxN];

void enter() {
    cin >> R >> C;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int x, y;
        cin >> x >> y;
        xmin = min(xmin, x);
        xmax = max(xmax, x);
        ymin = min(ymin, y);
        ymax = max(ymax, y);
    }
}

llint pw(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x % INF;
    llint res = pw(x, n / 2);
    res = res * res % INF;
    if (n & 1) res = res * x % INF;
    return res;
}

inline llint getC(int x, int n) {
    if (x == 0) return 1;
    if (x == n) return 1;
    //n! / (x! * (n - x)!)

    return gt[n] * pw(gt[x], (INF - 2)) % INF * pw(gt[n - x], (INF - 2)) % INF;
}

void solve() {
    gt[0] = 1;
    for (int i = 1; i <= R * C; ++i) {
        gt[i] = gt[i - 1] * i % INF;
    }
    int r = xmax - xmin + 1, c = ymax - ymin + 1;
    dp[r][c] = gt[r * c - N];
    for (int i = r; i <= R; ++i) {
        for (int j = c; j <= C; ++j) {
            //cout << i << " " << j << endl;
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * gt[j]) % INF;
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j] * gt[i]) % INF;
        }
    }

    llint res = dp[R][C];
    //cout << res << endl;
    res = res * getC(xmin - 1, R - xmax + xmin - 1) % INF;
    //cout << res << endl;
    res = res * getC(ymin - 1, C - ymax + ymin - 1) % INF;
    cout << res << endl;
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

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