ABC132D
考えたこと
要するにK個の青いボールをi個の非連続なグループにする並べ方を数え上げたい
グループの間には1個以上の赤いボールが入る
K個の青いボールをi個の非連続なグループにする
b_i = \binom{K-1}{i-1}
N-K個の赤いボールはi+1個のグループに分かれる、ただし両端は0になりうる
r_i = \binom{N-K+1}{i}
あとはこれをK件計算すれば良い
2000までの前計算をして高速化する
公式解説
方針OK
Kが2000と小さいので前計算せずにパスカルの三角形でもOKとのこと
AC
上記方針で素朴に実装するとriの計算でN - K - 1 < i になりうる。
数学的には0だが、コンビネーションの実装が想定してなくて、不正な値を返してWAした
ケアレスミスで時間を溶かさないようにライブラリの側でケアした
pythondef 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)"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]