AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC132 D - Blue and Red Balls

問題原文

atcoder.jp

問題要旨

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

解法

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

f:id:AT274:20200103153948p:plain
ステップ1:どの隙間を使うか

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

f:id:AT274:20200103154638p:plain
ステップ2:青い玉をどんな風にグループ分けするか

これは、  nCr(K - 1, i - 1) 通りになる。重複組み合わせっぽさがある考え方。

結局各 i についての答えは、  nCr(N - K + 1, i) * nCr(K - 1, i - 1) 通りになる。

実装

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)

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

感想

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