Submission #43054

#	Time	Username	Problem	Language	Result	Execution time	Memory
43054		ffresh	마스코트 (JOI13_mascots)	C++14	100 / 100	481 ms	36652 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;
}

int dp[N][N];



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;
	
	int dx=N,dy =N,ux=0,uy = 0;
	int r,c,n;
	cin>>r>>c>>n;
	assert(r<N && 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 = 1;

	for(int i=1;i<=tot;++i)
		ret= (ret*i)%mod;
	ret = (ret * combi(r-a,dx-1))%mod;
	ret = (ret*combi(c-b,dy-1))%mod;
	dp[0][0]=1;
	int x,y;
	int lx = r-a, ly = c-b;

	for(x=0;x<=lx;++x){
		for(y=0;y<=ly;++y){
			if(y<ly){
				ll temp = a+x;
				temp = per[temp];
				temp = (temp*dp[x][y])%mod;
				dp[x][y+1]= (dp[x][y+1]+ temp)%mod;
			}
			if(x<lx){
				ll temp = b+y;
				temp = per[temp];
				temp = (temp*dp[x][y])%mod;
				dp[x+1][y]= (dp[x+1][y]+ temp)%mod;
			}
		}
	}
	ret = (ret*dp[lx][ly])%mod;
	cout<<ret<<endl;
}	

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