Submission #35242

#TimeUsernameProblemLanguageResultExecution timeMemory
35242wan2000마스코트 (JOI13_mascots)C++14
100 / 100
276 ms213844 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3003; const ll MOD = 1e9+7; int row, col, n; ll F[N][N], Fac[N*N], BC[N][N], res; void init(){ Fac[0] = 1; for(int i = 1; i <= row*col; i++) Fac[i] = (Fac[i-1]*(ll)i)%MOD; for(int i = 0; i <= max(row,col); i++) BC[0][i] = 1; for(int i = 1; i <= max(row,col); i++){ BC[i][i] = 1; for(int j = i+1; j <= max(row,col); j++){ BC[i][j] = (BC[i-1][j-1]+BC[i][j-1])%MOD; } } } ll f(int x, int y, int r, int c){ if(F[x][y]) return F[x][y]; if(x==r&&y==c) return 1; ll ret = 0; if(x>r) ret = (ret+f(x-1,y,r,c)*Fac[y])%MOD; if(y>c) ret = (ret+f(x,y-1,r,c)*Fac[x])%MOD; return F[x][y] = ret; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>row>>col; init(); cin>>n; int u = N, v = N, p = 0, q = 0; for(int i = 1; i <= n; i++){ int x, y; cin>>x>>y; u = min(u,x); v = min(v,y); p = max(p,x); q = max(q,y); } int x = p-u+1; int y = q-v+1; ll need = (Fac[x*y-n]*f(row,col,x,y))%MOD; res = (BC[u-1][row-x]*BC[v-1][col-y])%MOD; res = (res*need)%MOD; cout<<res<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...