Blue and Red Balls [AtCoder Beginner Contest 132 D]

https://atcoder.jp/contests/abc132/tasks/abc132_d

• mod上での二項定理

解説

https://atcoder.jp/contests/abc132/submissions/6191711

この問題はmod上で二項定理を解く方法が分からないと解くことができない。
そちらをまずは勉強しよう。
　
今回のちょうどi回操作をすると青いボールをすべて回収できるという条件を言い換えると、
青ボールが連続する区間がちょうどi個あるという条件になる。
よって、各iについて、そのような条件を満たす並びを計算すればいい。
　
N=6でi=2の場合を考えてみると、
青赤青
というのは最小構成になる。
あとは、

• 残りの青を2グループある青にどう分配するか
• 残りの赤を3グループ（間の赤と左右の部分）にどう分配するか

という組み合わせになる。
これら2つはコンビネーションで計算可能。
　
R := 赤ボールの数
B := 青ボールの数
i := 青グループの数
とすると、最小構成で使われたあとでは、
r=R-(i-1) := 赤ボールの残り
b=B-i := 青ボールの残り
となり、組み合わせは

• 残りの青をiグループある青にどう分配するか → H(i, b)
• 残りの赤をi+1グループ（間の赤と左右の部分）にどう分配するか → H(i+1,r)

となるので、H(i, b)*H(i+1,r)が答えになる。

int N, K;
Comb<mint, 4040> com;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;

	int B = K;
	int R = N - K;

	rep(i, 1, K + 1) {
		int r = R - (i - 1);
		int b = B - i;

		mint ans = com.nHk(i, b) * com.nHk(i + 1, r);
		printf("%d\n", ans.get());
	}
}