AtCoder Regular Contest 058 D - いろはちゃんとマス目 / Iroha and a Grid

問題

arc058.contest.atcoder.jp

解法

左上の座標を (1, 1), 右下の座標を (H, W) とします(座標は (y, x) )。

y 座標が H-A+1 に初めて到達したときの x 座標の値で場合分けします。

y 座標が H-A+1 に初めて到達したときの x 座標が i ( > B) であるとすると,

• (1, 1) から (H-A, i) に行く
• (H-A, i) から (H-A+1, i) に行く
• (H-A+1, i) から (H, W) に行く

という風に行くことになります。この場合分けは重複して経路を数えないので, この経路を数えましょう。

ll mod_pow(ll x, ll p, ll MOD) {
    ll a = 1;
    while (p) {
        if (p%2) a = a*x%MOD;
        x = x*x%MOD;
        p/=2;
    }
    return a;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    return mod_pow(a, m-2, m);
}

const int MOD = 1e9+7;

const int MAX = 333333;
ll fact[MAX], rfact[MAX];

ll nCr(int n, int r) {
    return fact[n]*rfact[r]%MOD*rfact[n-r]%MOD;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact[0] = rfact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = (fact[i-1]*i)%MOD;
        rfact[i] = mod_inverse(fact[i], MOD);
    }
    int H, W, A, B;
    cin >> H >> W >> A >> B;
    ll ans = 0;
    for (int i = B+1; i <= W; i++) {
        int h = H-A-1, w = i-1;
        ll tmp = nCr(h+w, h);
        h = A-1, w = W-i;
        tmp *= nCr(h+w, w);
        ans += tmp%MOD;
    }
    cout << ans%MOD << endl;
    return 0;
}