oj.uz

답안 #35242

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
35242 2017-11-19T08:27:55 Z wan2000 마스코트 (JOI13_mascots) C++14
100 / 100
 276 ms 213844 KB 
#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;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 213536 KB Output is correct
2 Correct 0 ms 213536 KB Output is correct
3 Correct 0 ms 213536 KB Output is correct
4 Correct 0 ms 213536 KB Output is correct
5 Correct 0 ms 213536 KB Output is correct
6 Correct 0 ms 213536 KB Output is correct
7 Correct 0 ms 213536 KB Output is correct
8 Correct 0 ms 213536 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 213536 KB Output is correct
2 Correct 0 ms 213536 KB Output is correct
3 Correct 0 ms 213536 KB Output is correct
4 Correct 0 ms 213536 KB Output is correct
5 Correct 0 ms 213536 KB Output is correct
6 Correct 0 ms 213536 KB Output is correct
7 Correct 0 ms 213536 KB Output is correct
8 Correct 0 ms 213536 KB Output is correct
9 Correct 0 ms 213536 KB Output is correct
10 Correct 0 ms 213536 KB Output is correct
11 Correct 0 ms 213536 KB Output is correct
12 Correct 0 ms 213536 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 213536 KB Output is correct
2 Correct 0 ms 213536 KB Output is correct
3 Correct 3 ms 213536 KB Output is correct
4 Correct 13 ms 213544 KB Output is correct
5 Correct 23 ms 213536 KB Output is correct
6 Correct 36 ms 213536 KB Output is correct
7 Correct 29 ms 213536 KB Output is correct
8 Correct 53 ms 213568 KB Output is correct
9 Correct 103 ms 213536 KB Output is correct
10 Correct 259 ms 213844 KB Output is correct
11 Correct 186 ms 213756 KB Output is correct
12 Correct 103 ms 213536 KB Output is correct
13 Correct 9 ms 213536 KB Output is correct
14 Correct 96 ms 213536 KB Output is correct
15 Correct 256 ms 213832 KB Output is correct
16 Correct 219 ms 213788 KB Output is correct
17 Correct 123 ms 213536 KB Output is correct
18 Correct 276 ms 213832 KB Output is correct