Submission #34029

#	Time	Username	Problem	Language	Result	Execution time	Memory
34029		Dat160601	마스코트 (JOI13_mascots)	C++14	100 / 100	199 ms	150780 KiB

mascots

#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long mod=1e9+7;
long long r,c,mul[10000007],dp[3007][3007],ans=0,lx=0,ly=0,rx=0,ry=0,x,y;
int n;
long long ml(long long a,long long b){
	if(b==1) return a;
	long long res=ml(a,b/2);
	if(b%2==0) return (res*res)%mod;
	else return (((res*res)%mod)*a)%mod;
}
long long cal(long long k,long long n){
	if(k==0 || n==k) return 1LL;
	if(k>n) return 0LL;
	return (((mul[n]*ml(mul[k],mod-2))%mod)*ml(mul[n-k],mod-2))%mod;
}
signed main(){
	//ios_base::sync_with_stdio(0);
	cin>>r>>c;
	cin>>n;
	lx=r;
	ly=c;
	for(int i=1;i<=n;i++){
		cin>>x>>y;
		lx=min(lx,x);
		ly=min(ly,y);
		rx=max(rx,x);
		ry=max(ry,y);
	}
	mul[0]=1;
	for(long long i=1;i<=9000000;i++){
		mul[i]=mul[i-1]*i;
		mul[i]%=mod;
	}
	dp[0][0]=mul[(rx-lx+1)*(ry-ly+1)-n];
	for(int i=0;i<=r-(rx-lx+1);i++){
		for(int j=0;j<=c-(ry-ly+1);j++){
			dp[i+1][j]=(dp[i+1][j]+dp[i][j]*mul[c-j])%mod;
			dp[i][j+1]=(dp[i][j+1]+dp[i][j]*mul[r-i])%mod;
		}
	}
	ans=dp[r-(rx-lx+1)][c-(ry-ly+1)];
	ans=(ans*cal(lx-1,r-(rx-lx+1)))%mod;
	ans=(ans*cal(ly-1,c-(ry-ly+1)))%mod;
	cout<<ans;
}

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