Submission #414899

#	Time	Username	Problem	Language	Result	Execution time	Memory
414899		Pro_ktmr	마스코트 (JOI13_mascots)	C++17	100 / 100	214 ms	72184 KiB

mascots

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60