問題

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

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

atcoder.jp

記録

• 2022/3/15 解法わからず。

解法

• マス目を移動するパターンの数は \({}_{H + W} C_{H}\) か \({}_{H + W} C_{W}\) で計算する。計算しやすい方を使う。
• 下図、「ここは必ず通る」で分けて計算する。
  
• すなわち、
  S から B+1 へ行くパターンは何通りか？ × B+1 から Gへ行くパターンは何通りか？
  S から B+2 へ行くパターンは何通りか？ × B+2 から Gへ行くパターンは何通りか？
  …
  S から B+x へ行くパターンは何通りか？ × B+x から Gへ行くパターンは何通りか？
  
• S から B+1 へ行くパターンは何通りか？など上の部分の計算はダブる部分がある（左端を除く1つ左の計算結果）ので、引き算する必要がある。
• B+1 から Gへ行くパターンは何通りか？など下の部分の計算はダブらない。

コード例

#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;
}