oj.uz

Submission #414899

# Submission time Handle Problem Language Result Execution time Memory
414899 2021-05-31T10:31:33 Z Pro_ktmr 마스코트 (JOI13_mascots) C++17
100 / 100
 214 ms 72184 KB 
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

template<typename T>
T power(T x, long long n, const T &m){
    if(n == 0) return 1;
    if(n == 1) return x;
    T tmp = power(x, n/2, m);
    if(n%2 == 0) return tmp * tmp % m;
    else return tmp * tmp % m * x % m;
}

template<typename T>
T inverse(T x, const T &m){
    return power(x, m-2, m);
}

int H, W, N;

ll fact[3001];

ll dp[3001][3001];
ll solve(int h, int w){
	if(h == H && w == W) return 1;
	if(dp[h][w] != -1) return dp[h][w];
	ll ret = 0;
	if(h < H) ret += fact[w]*solve(h+1, w);
	if(w < W) ret += fact[h]*solve(h, w+1);
	return dp[h][w] = ret % MOD;
}

signed main(){
	cin >> H >> W >> N;
	int l = INT_MAX;
	int r = INT_MIN;
	int u = INT_MAX;
	int d = INT_MIN;
	rep(i, N){
		int y, x;
		cin >> y >> x;
		l = min(l, x-1);
		r = max(r, x-1);
		u = min(u, y-1);
		d = max(d, y-1);
	}

	fact[0] = 1;
	rep(i, 3000) fact[i+1] = fact[i]*(i+1)%MOD;
	memset(dp, -1, sizeof(dp));
	ll ans = 1;
	rep(i, (r-l+1)*(d-u+1)-N){ //ans*=(穴の数)!
		ans *= (i+1);
		ans %= MOD;
	}
	ans *= solve(d-u+1, r-l+1);
	ans %= MOD;
	rep(i, u){ //ans*=(H-h)C(u)
		ans *= H-(d-u+1)-i;
		ans %= MOD;
		ans *= inverse((ll)(i+1), MOD);
		ans %= MOD;
	}
	rep(i, l){ //ans*=(W-w)C(l)
		ans *= W-(r-l+1)-i;
		ans %= MOD;
		ans *= inverse((ll)(i+1), MOD);
		ans %= MOD;
	}
	cout << ans << endl;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
mascots.cpp:44:2: note: in expansion of macro 'rep'
   44 |  rep(i, N){
      |  ^~~
mascots.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
mascots.cpp:54:2: note: in expansion of macro 'rep'
   54 |  rep(i, 3000) fact[i+1] = fact[i]*(i+1)%MOD;
      |  ^~~
mascots.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
mascots.cpp:57:2: note: in expansion of macro 'rep'
   57 |  rep(i, (r-l+1)*(d-u+1)-N){ //ans*=(穴の数)!
      |  ^~~
mascots.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
mascots.cpp:63:2: note: in expansion of macro 'rep'
   63 |  rep(i, u){ //ans*=(H-h)C(u)
      |  ^~~
mascots.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
mascots.cpp:69:2: note: in expansion of macro 'rep'
   69 |  rep(i, l){ //ans*=(W-w)C(l)
      |  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70796 KB Output is correct
2 Correct 31 ms 70732 KB Output is correct
3 Correct 31 ms 70692 KB Output is correct
4 Correct 31 ms 70724 KB Output is correct
5 Correct 32 ms 70716 KB Output is correct
6 Correct 31 ms 70728 KB Output is correct
7 Correct 34 ms 70772 KB Output is correct
8 Correct 36 ms 70744 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 70784 KB Output is correct
2 Correct 35 ms 70796 KB Output is correct
3 Correct 33 ms 70680 KB Output is correct
4 Correct 34 ms 70724 KB Output is correct
5 Correct 38 ms 70732 KB Output is correct
6 Correct 39 ms 70712 KB Output is correct
7 Correct 38 ms 70736 KB Output is correct
8 Correct 37 ms 70704 KB Output is correct
9 Correct 34 ms 70756 KB Output is correct
10 Correct 35 ms 70732 KB Output is correct
11 Correct 53 ms 70828 KB Output is correct
12 Correct 34 ms 70732 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 70724 KB Output is correct
2 Correct 33 ms 70724 KB Output is correct
3 Correct 35 ms 70800 KB Output is correct
4 Correct 55 ms 70824 KB Output is correct
5 Correct 43 ms 70888 KB Output is correct
6 Correct 106 ms 71620 KB Output is correct
7 Correct 38 ms 70872 KB Output is correct
8 Correct 38 ms 70932 KB Output is correct
9 Correct 95 ms 71316 KB Output is correct
10 Correct 178 ms 71216 KB Output is correct
11 Correct 108 ms 71124 KB Output is correct
12 Correct 113 ms 71364 KB Output is correct
13 Correct 40 ms 70744 KB Output is correct
14 Correct 86 ms 70728 KB Output is correct
15 Correct 201 ms 71996 KB Output is correct
16 Correct 124 ms 71060 KB Output is correct
17 Correct 100 ms 71280 KB Output is correct
18 Correct 214 ms 72184 KB Output is correct