AtCoder Beginner Contest 132 D – Blue and Red Balls をPython3で解く

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Beginner Contest 132 D – Blue and Red Balls

この問題のように、何パターンかの通り数をパターン別に全て求める~といったときは、事前計算が必要になることが多い。

# AtCoder Beginner Contest 132 D - Blue and Red Balls
# https://atcoder.jp/contests/abc132/tasks/abc132_d
# tag: 数え上げ 二項定理 パスカルの三角形 MOD 順列・組み合わせ 高橋君 すぬけ君

# 青が i 個の塊になっている必要がある。
# 仮に i = 2 の場合の通り数を見つつ、一般化を試みる。

# 最終的には、
# (0個以上の赤) (1個以上の青) (1個以上の赤) (1個以上の青) (0個以上の赤)
# となっている必要がある。

# あらかじめ 1 個以上必要なところに 1 個置いておくとすると、
# i 個の青と i-1 個の赤が配置済みになる。
# その上で考える必要があるのは、
# n: 残った K-i 個の青を、i 個の場所へと重複ありで置く通り数
# m: 残った N-K-(i-1) 個の赤を、i+1 個の場所へと重複ありで置く通り数
# この n * m が、最終的な通り数となる。

# これらはそれぞれ
# n = (K-i + (i-1))! / ((K-i)! (i-1)!)
#   = (K-1)! / ((K-i)! (i-1)!)
#   = K-1 C i-1

# m = (N-K-(i-1) + i+1-1)! / ((N-K-(i-1) + i+1-1)! (i+1-1)!)
#   = (N-K+1) / ((N-K+1)! i!)
#   = N-K+1 C i

# これを素早く求められるように、あらかじめパスカルの三角形を
# 用いて準備しておく。

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

    # パスカルの三角形を用いて、
    # comb[i][j] = i C j となるようなテーブルを
    # 作成しておく。
    comb = [[0] * (N+1) for _ in range(N+1)]
    comb[0][0] = 1
    for i in range(1, N+1):
        for j in range(N+1):
            if j == 0:
                comb[i][j] = 1
            else:
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD

    # 考察より、答えを求める。
    for i in range(1, K+1):
        result = (comb[K-1][i-1] * comb[N-K+1][i]) % MOD
        print(result)

main()
Share

コメントを残す

メールアドレスが公開されることはありません。