oj.uz

Submission #766123

# Submission time Handle Problem Language Result Execution time Memory
766123 2023-06-25T10:29:51 Z bachhoangxuan 마스코트 (JOI13_mascots) C++17
100 / 100
 103 ms 66952 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 3005
#define int long long
const int mod=1e9+7;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=(res*a)%mod;
        a=(a*a)%mod;n>>=1;
    }
    return res;
}
int f(int n){
    int res=1;
    for(int i=2;i<=n;i++) res=(res*i)%mod;
    return res;
}
int fac[maxn],dfac[maxn];
int C(int k,int n){
    return fac[n]*dfac[k]%mod*dfac[n-k]%mod;
}
int x,y,u,v,n,m,q,dp[maxn][maxn];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m >> q;fac[0]=dfac[0]=1;
    for(int i=1;i<=max(n,m);i++){
        fac[i]=fac[i-1]*i%mod;
        dfac[i]=dfac[i-1]*power(i,mod-2)%mod;
    }
    x=n;y=m;
    for(int i=1;i<=q;i++){
        int a,b;cin >> a >> b;
        x=min(x,a);y=min(y,b);
        u=max(u,a);v=max(v,b);
    }
    int r=x-1+n-u,c=y-1+m-v,num=(u-x+1)*(v-y+1)-q;
    int ans=f(num)*C(n-u,r)%mod*C(m-v,c)%mod;
    for(int i=0;i<=r;i++){
        for(int j=0;j<=c;j++){
            if(i==0 && j==0){dp[i][j]=1;continue;}
            if(i>=1) dp[i][j]=(dp[i][j]+dp[i-1][j]*fac[v-y+j+1])%mod;
            if(j>=1) dp[i][j]=(dp[i][j]+dp[i][j-1]*fac[u-x+i+1])%mod;
        }
    }
    ans=ans*dp[r][c]%mod;
    cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 10 ms 9420 KB Output is correct
5 Correct 9 ms 8148 KB Output is correct
6 Correct 16 ms 6228 KB Output is correct
7 Correct 5 ms 1876 KB Output is correct
8 Correct 1 ms 404 KB Output is correct
9 Correct 32 ms 924 KB Output is correct
10 Correct 89 ms 66620 KB Output is correct
11 Correct 60 ms 44960 KB Output is correct
12 Correct 42 ms 1000 KB Output is correct
13 Correct 3 ms 2260 KB Output is correct
14 Correct 39 ms 340 KB Output is correct
15 Correct 96 ms 66952 KB Output is correct
16 Correct 67 ms 49940 KB Output is correct
17 Correct 36 ms 5212 KB Output is correct
18 Correct 103 ms 64104 KB Output is correct