ABC132 D - Blue and Red Balls
問題原文
問題要旨
個の玉がある。そのうち
個が青い玉で、
個が青い玉である。
これら 個の玉を横一列に並べることを考える時、
を満たす全ての
について、「青い玉が1個以上連続する区間がちょうど
個」であるような玉の並べ方の総数を求めよ。
解法
逆元コンビネーションは持っているものとする。
まず、赤い玉だけを並べて、その隙間に青い玉を並べることを考える。どの隙間を使うかは、 通り。
次に、青い玉をどう並べるかを考える。
これは例えば、 青い玉4つを3グループに分けるには、「青い玉の隙間に2つの仕切りを入れる」と考えるとわかりやすい。
これは、 通りになる。重複組み合わせっぽさがある考え方。
結局各 についての答えは、
通りになる。
実装
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)
逆元コンビネーションの実装は省いてます。
感想
少し苦手。。。 落ち着いて、構造を分解していこう。