Submission #1242943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242943		tvgk	마스코트 (JOI13_mascots)	C++20	100 / 100	1588 ms	206776 KiB

mascots

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e3 + 2, MOD = 1e9 + 7;

int nRow, nCol, n;
ll gt[mxN * mxN], rev[mxN * mxN], dp[mxN][mxN];

ll pw(int j, int mx)
{
    if (!mx)
        return 1;

    ll res = pw(j, mx / 2);
    res = res * res % MOD;
    if (mx % 2)
        return res * j % MOD;
    return res;
}

ll C(int u, int v)
{
    return gt[v] * rev[u] % MOD * rev[v - u] % MOD;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> nRow >> nCol;
    cin >> n;
    ii l, r;
    for (int i = 1; i <= n; i++)
    {
        ii tmp;
        cin >> tmp.fi >> tmp.se;

        if (i == 1)
            l = r = tmp;

        l.fi = min(l.fi, tmp.fi);
        l.se = min(l.se, tmp.se);
        r.fi = max(r.fi, tmp.fi);
        r.se = max(r.se, tmp.se);
    }

    gt[0] = rev[0] = 1;
    for (int i = 1; i <= nRow * nCol; i++)
    {
        gt[i] = gt[i - 1] * i % MOD;
        rev[i] = pw(gt[i], MOD - 2) % MOD;
    }

    dp[r.fi - l.fi + 1][r.se - l.se + 1] = gt[(r.fi - l.fi + 1) * (r.se - l.se + 1) - n];
    for (int i = r.fi - l.fi + 1; i <= nRow; i++)
    {
        for (int j = r.se - l.se + 1; j <= nCol; j++)
        {
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j] * gt[i]) % MOD;
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * gt[j]) % MOD;
        }
    }
    cout << dp[nRow][nCol] * C(nRow - r.fi, nRow - (r.fi - l.fi + 1)) % MOD * C(nCol - r.se, nCol - (r.se - l.se + 1)) % MOD;
}

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