ABC132D

D - Blue and Red Balls

• 
• 考えたこと
  • 要するにK個の青いボールをi個の非連続なグループにする並べ方を数え上げたい
  • グループの間には1個以上の赤いボールが入る
  • K個の青いボールをi個の非連続なグループにする
    • 
    • $b_i=\left(\genfrac{}{}{0ex}{}{K-1}{i-1}\right)$
  • N-K個の赤いボールはi+1個のグループに分かれる、ただし両端は0になりうる
    • 
    • $r_i=\left(\genfrac{}{}{0ex}{}{N-K+1}{i}\right)$
  • あとはこれをK件計算すれば良い
    • 2000までの前計算をして高速化する
• 公式解説
  • 方針OK
  • Kが2000と小さいので前計算せずにパスカルの三角形でもOKとのこと
• AC
  • 上記方針で素朴に実装するとriの計算でN - K - 1 < i になりうる。
    • 数学的には0だが、コンビネーションの実装が想定してなくて、不正な値を返してWAした
    • ケアレスミスで時間を溶かさないようにライブラリの側でケアした python

def main():
    N, K = map(int, input().split())
    MOD = 1_000_000_007
    c = Combination(N, MOD)
    for i in range(1, K + 1):
        r = c.comb(K - 1, i - 1)
        r *= c.comb(N - K + 1, i)
        r %= MOD
        print(r)