ABC042 D - いろはちゃんとマス目 (400)
下からA+1番目で左からB+1番からW番までのそれぞれの点について左上から到達できるパターンを求める
下からA番目で左からB+1番からW番までのそれぞれの点について右下から到達できるパターンを求める
両方とも組み合わせを用いて計算できる
それぞれの点について
$ (左上からのパターン) \times (右上からのパターン)
を計算して足し合わせると過不足無く列挙できる
$ _nC_k
の事前計算がボトルネックで
$ O(H+W)
問題:
https://atcoder.jp/contests/abc042/tasks/arc058_b
提出:
https://atcoder.jp/contests/abc042/submissions/15398532
#ABC042
#400pt
#D
#ABC
#AtCoder
#組み合わせ