ABC042 D いろはちゃんとマス目

Question

abc042.contest.atcoder.jp

やること

Abstruct

長方形の通れない場所の右の部分と上の部分の2つに分割して、
の経路の数を, すべてので計算して, sumすればよい。(上下にわけられた長方形の間の移動は, 1通りの経路のみ)

へ移動する経路の数は,

で求めることができる。
これは、 で前処理をしておいて, 後でで求める

その具体的な方法は http://hos.ac/slides/20130319_enumeration.pdf この記事を参照するとわかりやすい.

ここでは深く言及しない。

SourceCode

const int MOD = 1e9 + 7;
 
// x^n % mod
// O(log n)
template<typename T>
T mod_pow(T x, T n, T mod) {
	T res = 1;
	while (n > 0) {
		if (n & 1) res = res * x & mod;
		x = x*x %mod;
		n >>= 1;
	}
	return res;
}
 
// fact(n)%MOD, invFact(n)%MOD, inv(n)%MOD, nCk
// Constructor O(N)
// other O(1)
template<typename T, int MOD>
class Choose {
public:
	vector<T> fact, inv, invFact;
 
	Choose(T N):fact(N), inv(N), invFact(N){
		inv[1] = 1;
		FOR(i, 2, inv.size()) inv[i] = MOD - (MOD / i) * inv[MOD%i] % MOD;
		fact[0] = invFact[0] = 1;
		FOR(i, 1, fact.size()) {
			fact[i] = fact[i - 1] * i % MOD;
			invFact[i] = (invFact[i - 1] * inv[i]) % MOD;
		}
	}
 
	//Get nCk
	T operator () (T n, T k) const {
		if (not ((T)0 <= k and k <= n)) return 0;
		return (((fact[n] * invFact[k]) % MOD)*invFact[n - k]) % MOD;
	}
};
 
ll f(ll x , ll y, const Choose<ll, MOD>& c) {
	return c(x + y, x);
}
 
signed int main(void) {
	ll H, W, A, B; cin >> H >> W >> A >> B;
	Choose<ll, MOD> c(H + W);
 
	ll ans = 0;
	FOR(i, B, W + 1) {
		ans += f(H - A - 1, i, c) * f(A - 1, W - 1 - i, c);
		ans %= MOD;
	}
 
	cout << ans << endl;
 
	return 0;
}