D - いろはちゃんとマス目 別解（NGな通路を引くVER）

• Quiz
  • https://atcoder.jp/contests/abc042/tasks/arc058_b
• AC
  • https://atcoder.jp/contests/abc042/submissions/22539182
• 解説
  • NG領域を考慮しない場合の数を求める
  • NG領域を通る領域の場合の数を引く
  • ここでNG領域の数え方だが、下図のようにNG領域の角から左下に降りていく❌を通る方法としてそれぞれ求めれば重複がない

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // 座標は1-indexed
    // 下方向をy
    // 右方向をx

    // nCrテーブルは作られているとする

    // input
    ll h,w,a,b;
    cin>>h>>w>>a>>b;

    ll mi = min(a,b);

    mint sum = nCr(h+w-2,w-1);

    // 左下の分を引く
    ll y = h-a+1;
    ll x = b;
    rep(i,mi){
      // 前半
      mint m = nCr(y+x-2,x-1);
      
      // 後半
      ll dy = h-y;
      ll dx = w-x;
      m *= nCr(dy+dx,dx);

      sum -= m;

      y++;
      x--;
    }
    p(sum.x);
    
    return 0;
}