| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43054 |
2018-03-08T11:20:17 Z |
ffresh |
마스코트 (JOI13_mascots) |
C++14 |
|
481 ms |
36652 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
248 KB |
Output is correct |
| 2 |
Correct |
1 ms |
352 KB |
Output is correct |
| 3 |
Correct |
1 ms |
388 KB |
Output is correct |
| 4 |
Correct |
1 ms |
404 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Correct |
1 ms |
532 KB |
Output is correct |
| 7 |
Correct |
1 ms |
532 KB |
Output is correct |
| 8 |
Correct |
1 ms |
548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
548 KB |
Output is correct |
| 2 |
Correct |
1 ms |
548 KB |
Output is correct |
| 3 |
Correct |
1 ms |
548 KB |
Output is correct |
| 4 |
Correct |
1 ms |
548 KB |
Output is correct |
| 5 |
Correct |
1 ms |
552 KB |
Output is correct |
| 6 |
Correct |
2 ms |
552 KB |
Output is correct |
| 7 |
Correct |
2 ms |
676 KB |
Output is correct |
| 8 |
Correct |
2 ms |
676 KB |
Output is correct |
| 9 |
Correct |
2 ms |
688 KB |
Output is correct |
| 10 |
Correct |
1 ms |
688 KB |
Output is correct |
| 11 |
Correct |
2 ms |
688 KB |
Output is correct |
| 12 |
Correct |
1 ms |
688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
688 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1004 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1772 KB |
Output is correct |
| 4 |
Correct |
47 ms |
6932 KB |
Output is correct |
| 5 |
Correct |
42 ms |
6932 KB |
Output is correct |
| 6 |
Correct |
75 ms |
6932 KB |
Output is correct |
| 7 |
Correct |
13 ms |
6932 KB |
Output is correct |
| 8 |
Correct |
4 ms |
6932 KB |
Output is correct |
| 9 |
Correct |
97 ms |
6932 KB |
Output is correct |
| 10 |
Correct |
441 ms |
35412 KB |
Output is correct |
| 11 |
Correct |
292 ms |
35412 KB |
Output is correct |
| 12 |
Correct |
93 ms |
35412 KB |
Output is correct |
| 13 |
Correct |
10 ms |
35412 KB |
Output is correct |
| 14 |
Correct |
60 ms |
35412 KB |
Output is correct |
| 15 |
Correct |
473 ms |
36652 KB |
Output is correct |
| 16 |
Correct |
352 ms |
36652 KB |
Output is correct |
| 17 |
Correct |
84 ms |
36652 KB |
Output is correct |
| 18 |
Correct |
481 ms |
36652 KB |
Output is correct |
