Submission #43070

#	Time	Username	Problem	Language	Result	Execution time	Memory
43070		smu201111192	마스코트 (JOI13_mascots)	C++14	0 / 100	99 ms	71164 KiB

mascots

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 3005;
int r,c,n,yy,xx;
int mny,mxy,mnx,mxx;
long long fact[MAXN],dp[MAXN][MAXN];
const long long mod = 1000000007;

long long distribute(int l,int r){
    long long &ret = dp[l][r];
    if(ret != -1) return ret;
    if(l == 0 && r == 0) return ret = 1;
    ret = 0;
    if(l > 0) ret += distribute(l-1,r);
    if(r > 0) ret += distribute(l,r-1);
    ret %= mod;
    return ret;
}
long long go(int remain,int start,int limit){
    memset(dp,0,sizeof(dp));
    dp[0][start] = 1;
    for(int i = 1; i <= remain; i++){
        long long sm = 0;
        for(int j = start; j <= limit; j++){
            sm += dp[i-1][j]; sm %= mod;
            dp[i][j] = sm * fact[j]; dp[i][j] %= mod;
        }
    }
    long long ret = 0;
    for(int j = start; j <= limit; j++){
        ret += dp[remain][j];
        ret %= mod;
    }
    return ret;
}
long long getCnt(int low,int high){
    memset(dp,-1,sizeof(dp));
    return distribute(low,high);
}
long long mul(long long a,long long b){
    return (a * b) % mod;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> r >> c >> n;
    mny = mnx = 2e9;
    mxy = mxx = -2e9;
    for(int i = 1; i <= n; i++){
        cin >> yy >> xx;
        mny = min(mny,yy);
        mxy = max(mxy,yy);
        mnx = min(mnx,xx);
        mxx = max(mxx,xx);
    }
    long long tot = (mxy - mny + 1) * (mxx - mnx + 1) - n;
    fact[0] = 1;
    for(int i = 1; i <= 3000; i++) {fact[i] = fact[i-1] * i; fact[i] %= mod;}
    int lx = mnx - 1; int rx = c - mxx;
    int ly = mny - 1; int ry = r - mxy;
    long long ycnt = getCnt(ly,ry);
    long long xcnt = getCnt(lx,rx);
    long long yfact = go(c - (mxx - mnx +1),mxy - mny + 1,r);
    long long xfact = go(r - (mxy - mny +1),mxx - mnx + 1,c);
    long long ans = mul(ycnt,xcnt);
    ans = mul(ans,yfact);
    ans = mul(ans,xfact);
    ans = mul(ans,fact[tot]);
    cout<<ans;
    
    
    
    return 0;
}

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