Submission #1126681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126681		underwaterkillerwhale	마스코트 (JOI13_mascots)	C++20	100 / 100	251 ms	104528 KiB

mascots

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 3e3 + 7;
const int Mod = 1e9 + 7;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 450;

inline void Add (int &A, int B) {
    A += B;
    if (A >= Mod) A -= Mod;
}

inline void Sub (int &A, int B) {
    A -= B;
    if (A < 0) A += Mod;
}

int n, m, K;
pii a[N * N];
int fac[N * N];

int dp[N][N];
int C[N][N];

void solution() {
    cin >> n >> m;
    cin >> K;
    int x, y, u, v;
    rep (i, 1, K) {
        cin >> a[i].fs >> a[i].se;
        if (i == 1) {
            x = u = a[i].fs;
            y = v = a[i].se;
        }
        else {
            x = min(x, a[i].fs);
            y = min(y, a[i].se);
            u = max(u, a[i].fs);
            v = max(v, a[i].se);
        }
    }
    dp[u - x + 1][v - y + 1] = 1;
    fac[0] = 1;
    rep (i, 1, n * m) fac[i] = 1LL * fac[i - 1] * i % Mod;

    rep (i, 0, max(n, m)) {
        rep (j, 0, max(n, m)) {
            if (j == i || j == 0) {
                C[j][i] = 1;
                continue;
            }
            C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % Mod;
        }
    }

    rep (i, u - x + 1, n) {
        rep (j, v - y + 1, m) {
            Add(dp[i + 1][j], 1LL * dp[i][j] * fac[j] % Mod);
            Add(dp[i][j + 1], 1LL * dp[i][j] * fac[i] % Mod);
        }
    }
    int remRow = n - (u - x + 1), remCol = m - (v - y + 1);
    cout << 1LL * C[x - 1][remRow] * C[y - 1][remCol] % Mod * dp[n][m] % Mod * fac[(u - x + 1) * (v - y + 1) - K] % Mod <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +34
2 1
0 1
*/

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