oj.uz

Submission #43050

# Submission time Handle Problem Language Result Execution time Memory
43050 2018-03-08T11:05:46 Z ffresh 마스코트 (JOI13_mascots) C++14
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

const int N =9005,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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -