Atcoder ARC058B Iroha and a Grid

考虑从第 \(b\) 列与第 \(b + 1\) 之间分开这个矩阵，钦定 \((i, b)\) 下一步必须走到 \((i, b + 1)\)，可以发现这样是不会漏算或算重的。
于是就可以用乘法原理算出这个 \(i\) 的贡献：\(\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{(n - i) + (m - b - 1)}{n - i}\)，左半部分的就是 \((1, 1)\) 走到 \((i, b)\) 的方案数，右半部分就是 \((i, b + 1)\) 走到 \((n, m)\) 的方案数。
再用加法原理统计总答案：\(\sum\limits_{i = 1}^{n - a}\binom{(i - 1) + (b - 1)}{i - 1}\times \binom{(n - i) + (m - b - 1)}{n - i}\)。

时间复杂度 \(O(n + m)\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: D - Iroha and a Grid
// Contest: AtCoder - AtCoder Regular Contest 058
// URL: https://atcoder.jp/contests/arc058/tasks/arc058_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5;
ll fac[N + 5], inv[N + 5];
const ll mod = 1e9 + 7;
ll _inv(ll a) {
	ll b = mod - 2, val = 1;
	for (; b; b >>= 1, a = a * a % mod) {
		if (b & 1) {
			val = val * a % mod;
		}
	}
	return val;
}
ll C(int n, int m) {
	return fac[n] * inv[m] % mod * inv[n - m] % mod;
}
int main() {
	fac[0] = inv[0] = 1ll;
	for (int i = 1; i <= N; i++) {
		fac[i] = 1ll * fac[i - 1] * i % mod;
	}
	inv[N] = _inv(fac[N]);
	for (int i = N - 1; i; i--) {
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
	}
	int n, m, a, b;
	scanf("%d%d%d%d", &n, &m, &a, &b);
	long long ans = 0;
	for (int i = 1; i <= n - a; i++) {
		ans = (ans + C(i + b - 2, i - 1) * C(m - b - 1 + n - i, n - i) % mod) % mod; 
	}
	printf("%lld\n", ans);
	return 0;
}