Submission #1285023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285023		kerem	마스코트 (JOI13_mascots)	C++20	10 / 100	1 ms	580 KiB

mascots

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 3000
#define inf (int)1e15
typedef pair<int,int> pii;

const int mod=100000007;
int n,m,fac[N*N+5],dp[N+5][N+5];
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%mod;
}
int fp(int x,int y){
	int ans=1;
	for(;y;x=x*x%mod,y>>=1)
		if(y&1) ans=ans*x%mod;
	return ans;
}
int C(int n,int r){
	int a=fac[n];	
	int b=fac[r]*fac[n-r]%mod;
	return a*fp(b,mod-2)%mod;	
}
int calc(int x,int y){
	if(dp[x][y]) return dp[x][y];
	if(y<m) dp[x][y]+=fac[x]*calc(x,y+1)%mod;
	if(x<n) dp[x][y]+=fac[y]*calc(x+1,y)%mod;
	dp[x][y]%=mod;
	return dp[x][y];
}
void solve(){
	cin >> n >> m;
	init(n*m);
	int k;cin >> k;
	int x1=n,y1=m,x2=1,y2=1;
	for(int i=0;i<k;i++){
		int x,y;
		cin >> x >> y;
		x1=min(x1,x);
		x2=max(x2,x);
		y1=min(y1,y);
		y2=max(y2,y);
	}
	int X=x2-x1+1,Y=y2-y1+1;
	int ans=fac[X*Y-k];
	dp[n][m]=1;
	ans=ans*calc(X,Y)%mod;
	ans=ans*(C(n-X,x1-1)*C(m-Y,y1-1)%mod)%mod;
	cout << ans << "\n";
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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