TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

いろはちゃんとマス目

問題

D – いろはちゃんとマス目
プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

記録

解法

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
using mint = modint1000000007;
const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    assert(n < mod);
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
      fact[i] = fact[i - 1] * i;
    }
    ifact[n] = fact[n].inv();
    for(int i = n; i >= 1; i--) {
      ifact[i - 1] = ifact[i] * i;
    }
  }
  mint operator()(int n, int k) {
    if(k < 0 || k > n) {
      return 0;
    } else {
      return fact[n] * ifact[k] * ifact[n - k];
    }
  }
};

int main() {
  int H, W;
  cin >> H >> W;
  int A, B;
  cin >> A >> B;

  combination c(W + H + 5);

  mint area1 = 0;
  vector<mint> temp(W - B);
  vector<mint> ans(W - B);
  for(int i = B; i < W; ++i) {
    area1 = c(i + H - 1 - A, i);
    temp[i - B] = area1;
    if(i == B) {
      ans[i - B] = area1;
    } else {
      ans[i - B] = area1 - temp[i - B - 1];
    }
  }

  mint area2 = 0;
  for(int i = 0; i < W - B; ++i) {
    area2 = c(A + i, A);
    ans[W - B - i - 1] *= area2;
  }

  mint result = 0;
  int n = ans.size();
  rep(i, n) { result += ans[i]; }

  cout << result.val() << endl;
  return 0;
}