Submission #43049

#	Time	Username	Problem	Language	Result	Execution time	Memory
43049		ffresh	마스코트 (JOI13_mascots)	C++14	40 / 100	128 ms	142360 KiB

mascots

#include <bits/stdc++.h>

using namespace std;

const int N =3005,mod = 1e9+7;


#define ll long long

ll per[N];

ll mypow(ll x,ll c){
	ll ret=1;
	while(c){
		if(c&1)
			ret= (ret*x)%mod;

		x = (x*x)%mod;
		c>>=1;
	}
	return ret;
}

ll dp[N][N];


ll solve(int x,int y,int lx,int ly,int a,int b){

	if(x==lx && ly==y)return 1;

	ll &ret= dp[x][y];

	if(ret!=-1)return ret;

	ret = 0;

	if(y<ly){
		ll temp = a+x;
		temp = per[temp];
		ret = (ret + temp*solve(x,y+1,lx,ly,a,b))%mod;
	}
	if(x<lx){
		ll temp = b+y;

		temp = per[temp];
		ret= (ret + temp*solve(x+1,y,lx,ly,a,b))%mod;
	}
	return ret;
}

ll combi(int n,int c){
	ll ret= per[n];
	ret = (ret *mypow(per[c],mod-2))%mod;
	ret = (ret *mypow(per[n-c],mod-2))%mod;
	return ret;
}
int main(){
	//freopen("input.txt","r",stdin);
	per[0]= 1;
	for(int i=1;i<N;++i)per[i]=(per[i-1]*i)%mod;
	memset(dp,-1,sizeof(dp));
	int dx=N,dy =N,ux=0,uy = 0;
	int r,c,n;
	cin>>r>>c>>n;
	for(int i=0;i<n;++i){
		int u,v;
		cin>>u>>v;
		dx= min(dx,u),dy= min(dy,v);
		ux= max(ux,u),uy= max(uy,v);
	}
	int a = ux-dx+1;
	int b= uy-dy+1;
	int tot = a*b - n;
	
	ll ret = per[tot];

	ret = (ret * combi(r-a,dx-1))%mod;
	ret = (ret*combi(c-b,dy-1))%mod;

	ret= (ret * solve(0,0,r-a,c-b,a,b))%mod;
	cout<<ret<<endl;
}	

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