Submission #147112

#	Time	Username	Problem	Language	Result	Execution time	Memory
147112		red1108	마스코트 (JOI13_mascots)	C++17	100 / 100	905 ms	207892 KiB

mascots

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<utility>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<ext/rope>
#include<unordered_set>
#include<unordered_map>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define pb push_back
#define enter "\n" 
#define space " "
#define pr2(a,b) cout<<(a)<<" "<<(b)<<endl
#define pr3(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define pr4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define prec(a) cout<<fixed;cout.precision(a);
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
const ll INF = 1e18;
const int inf = 1e9;

int n, m,s=inf,e,hs=inf,he;
ll pac[9000010],mod=1000000007,ipac[9000010],dp[3010][3010],w,h;
ll mypow(ll a, ll b){
	ll ret=1;
	while(b){
		if(b&1) ret = ret*a%mod;
		a = a*a%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	fastio;
	cin>>n>>m;
	int p;
	cin>>p;
	for(int i=1;i<=p;i++){
		int a, b;
		cin>>a>>b;
		hs=min(hs,a);
		he=max(he,a);
		s=min(s,b);
		e=max(e,b);
	}
	pac[0]=1;
	for(int i=1;i<=n*m;i++) pac[i]=pac[i-1]*i%mod;
	ipac[n*m]=mypow(pac[n*m],mod-2);
	for(int i=n*m-1;i>=1;i--) ipac[i]=ipac[i+1]*(i+1)%mod;
	ipac[0]=1;
	w = e-s+1;
	h = he-hs+1;
	dp[h][w]=1;
	for(int i=h;i<=n;i++){
		for(int j=w;j<=m;j++){
			if(i==h&&j==w) continue;
			dp[i][j]=(dp[i-1][j]*pac[j]%mod+dp[i][j-1]*pac[i]%mod)%mod;
		}
	}
	ll ans = dp[n][m],ww=1,hh=1;
	ans = ans*pac[w*h-p]%mod;
	ww = pac[m-w]*ipac[s-1]%mod*ipac[m-e]%mod;
	hh = pac[n-h]*ipac[hs-1]%mod*ipac[n-he]%mod;
	ans = ans*ww%mod*hh%mod;
	cout<<ans;
}

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