問題
考えたこと
- 組み合わせ系の問題
- i = 1 を考えると 青いボールが連続して並んでいる場合だけ.
- 例えば赤いボールと青いボールがそれぞれ3個ずつあった場合には, 赤いボールの隙間に青いボール全部を入れることになるので
の組み合わせ.
- i = 2 を考えると 赤いボールの隙間のうち, 2箇所に青いボールを入れれば良いことがわかる. つまり
になるはず.
- 青いボールは分割した数 (i = 2 の場合2個) を取り除いて残ったボールの数に, 仕切りの数 (i = 2 なら 仕切りの数は1つ) を足したものの仕切りの位置を選ぶ組み合わせ.
- つまり2回で回収できる組み合わせは (赤いボールの隙間) *
(青いボールの割り振り方) で計算できる.
- 3回目以降も同様. ルール化できたので実装に入る.
実装
MOD = 10**9+7
def comb_mod(n, r, mod):
up = 1
down = 1
for i in range(r):
up *= n - i
up %= mod
down *= i + 1
down %= mod
return ((up * pow(down, mod - 2, mod)) % mod)
n, k = [int(x) for x in input().split()]
for i in range(1, k+1):
l = comb_mod(n-k+1, i, MOD)
r = comb_mod(k-1, i-1, MOD)
ans = (l * r) % MOD
print(ans)
結果
- 無事, 上記の考察で
AC できた
- 実装する前は, 青いボールは区別がないので 1, 2 と 2, 1 で分ける場合が同じになるか？と考えてしまった
- 実際に手計算して, どうやら重複組合せの考え方で問題なさそうなことを確認
- その後, 赤のボールの隙間を 名前のついた箱 だと思うことによって別物だと考えて良さそうと考え直す
