Submission #374927

#	Time	Username	Problem	Language	Result	Execution time	Memory
374927		Killer2501	마스코트 (JOI13_mascots)	C++14	100 / 100	1530 ms	207244 KiB

mascots

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "conststrfd"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
const ll mod = 1e9+7;
const ll N = 3005;
vector<ll> kq;
vector<pll> pre;
string s;
ll n, m, t, k, b[N*N], p, a[N*N], ans, tong, c, r, cnt;
ll dp[N][N];

ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

ll C(ll u, ll v)
{
    if(u > v)return 0;
    return a[v] * b[u] % mod * b[v-u]% mod;
}
void sol()
{
    cin >> r >> c >> n;
    a[0] = b[0]  = 1;
    for(int i = 1; i <= r*c; i ++)
    {
        a[i] = a[i-1] * i % mod;
        b[i] = b[i-1] * pw(i, mod-2) % mod;
    }
    ll posl = r, posr = c, posu = 1, posv = 1;
    for(int i = 1; i <= n;i ++)
    {
        ll u, v;
        cin >> u >> v;
        posl = min(posl, u);
        posu = max(posu, u);
        posr = min(posr, v);
        posv = max(posv, v);
    }
    ll u = posu-posl+1, v = posv-posr+1;
    dp[u][v] = a[u*v-n];
    for(int i = u; i <= r; i ++)
    {
        for(int j = v; j <= c; j ++)
        {
            if(i == u && j == v)continue;
            dp[i][j] = (dp[i-1][j] * a[j] + dp[i][j-1] * a[i]) % mod;

        }
    }
    //cout << dp[r][c] << '\n';
    cout << dp[r][c] * C(posl-1, r-u) % mod * C(posr-1, c-v) % mod;
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    for(int i = 1; i <= ntest; i ++)
    sol();
}
/*
5
5 4
1 2
1 3
4 1
5 1
7 0
8 8
1 2
2 3
3 4
4 1
1 6
6 7
7 8
8 6
4 4
1 2
2 3
1 4
4 3
4 4
1 2
2 3
1 3
3 4
*/

Compilation message (stderr)

mascots.cpp: In function 'int main()':
mascots.cpp:71:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   71 |        freopen(task".inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:72:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   72 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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