Submission #1023871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023871		MilosMilutinovic	마스코트 (JOI13_mascots)	C++14	100 / 100	210 ms	107356 KiB

mascots

#include <bits/stdc++.h>

using namespace std;

const int N = 3003 * 3003;
const int md = 1e9 + 7;

int f[N], inv[N];

int add(int x, int y) {
  return x + y < md ? x + y : x + y - md;
}

void sadd(int& x, int y) {
  x = add(x, y);
}

int mul(int x, int y) {
  return x * 1LL * y % md;
}

void smul(int& x, int y) {
  x = mul(x, y);
}

int ckpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) {
      ret = mul(ret, x);
    }
    x = mul(x, x);
    k >>= 1;
  }
  return ret;
}

int C(int n, int k) {
  if (n < 0 || k < 0 || n < k) {
    return 0;
  }
  return mul(f[n], mul(inv[k], inv[n - k]));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  f[0] = 1;
  for (int i = 1; i < N; i++) {
    f[i] = mul(f[i - 1], i);
  }
  inv[N - 1] = ckpow(f[N - 1], md - 2);
  for (int i = N - 2; i >= 0; i--) {
    inv[i] = mul(inv[i + 1], i + 1);
  }
  int r, c;
  cin >> r >> c;
  int n;
  cin >> n;
  int lx = r, rx = -1, ly = c, ry = -1;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    lx = min(lx, x);
    rx = max(rx, x);
    ly = min(ly, y);
    ry = max(ry, y);
  }
  int len_x = rx - lx + 1;
  int len_y = ry - ly + 1;
  int total = len_x * len_y - n;
  vector<vector<int>> dp(r + 1, vector<int>(c + 1));
  dp[len_x][len_y] = f[total];
  for (int x = 1; x <= r; x++) {
    for (int y = 1; y <= c; y++) {
      if (x < r) {
        sadd(dp[x + 1][y], mul(dp[x][y], f[y]));
      }
      if (y < c) {
        sadd(dp[x][y + 1], mul(dp[x][y], f[x]));
      }
    }
  }
  int res = dp[r][c];
  smul(res, C(r - len_x, lx - 1));
  smul(res, C(c - len_y, ly - 1));
  cout << res << '\n';
  return 0;
}

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