ABC132 D - Blue and Red Balls

問題原文

atcoder.jp

問題要旨

個の玉がある。そのうち 個が青い玉で、 個が青い玉である。
これら 個の玉を横一列に並べることを考える時、 を満たす全ての について、「青い玉が１個以上連続する区間がちょうど 個」であるような玉の並べ方の総数を求めよ。

解法

逆元コンビネーションは持っているものとする。
まず、赤い玉だけを並べて、その隙間に青い玉を並べることを考える。どの隙間を使うかは、 通り。

ステップ１：どの隙間を使うか

次に、青い玉をどう並べるかを考える。
これは例えば、 青い玉４つを３グループに分けるには、「青い玉の隙間に２つの仕切りを入れる」と考えるとわかりやすい。

ステップ２：青い玉をどんな風にグループ分けするか

これは、 通りになる。重複組み合わせっぽさがある考え方。

結局各 についての答えは、 通りになる。

実装

N, K = map(int, input().split())
MOD = 10 ** 9 + 7

for i in range(1, K + 1):
    print(nCr(N - K + 1, i) * nCr(K + i - 2, i - 1) % MOD)

逆元コンビネーションの実装は省いてます。

感想

少し苦手。。。 落ち着いて、構造を分解していこう。