The 高校数学（組み合わせ） - プニプニ精進記録

ABC132 D Blue and Red Balls

ABC132 D Blue and Red Balls

問題概要

$K$ 個の青ボールと $N-K$ 個の赤いボールが与えられる．これらのボールを一列に並べる．１回の操作で連続する青いボールは何個でも回収できる．この時， $K$ 個の青いボールを全て回収するのに $i$ 回操作を行う並べ方は何通りあるか，その答えを $10^9+7$ で割った余りを求めよ

問題リンク

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

制約

$1\leq N \leq K \leq 2000$

考察

高校数学の組み合わせ感があるので考える
i回操作しないといけないということは，青いボールをi個に分断してある必要がある．この組み合わせは，青いボールの間の個数 $K-1$ 箇所の中から $i-1$ 箇所選ぶ組み合わせになるので $_{K-1} \mathrm{C} _{i-1}$ 通り
これを赤ボールの間の個数 $N-K-1$ と両端の2か所の合計 $N-K+1$ 箇所から $i$ 箇所選んで埋め込めばいいので，この組み合わせは $_{N-K+1} \mathrm{C} _{i}$ 通り
青いボールの分断の仕方 $_{K-1} \mathrm{C} _{i-1}$ 通りに対して埋め込み方が $_{N-K+1} \mathrm{C} _{i}$ 通りあるので，i回の操作で青ボールを全て取りきることができる並べ方は $_{K-1} \mathrm{C} _{i-1} \times _{N-K+1} \mathrm{C} _{i}$ 通りとなるので各iについてこれを計算すればよい

ソースコード

※マクロは使っていないので無視してください

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };


struct Combination {

	vector<ll> fact, rfact;

	Combination(ll sz) : fact(sz + 1), rfact(sz + 1) {

		fact[0] = 1;
		for (ll i = 1; i < fact.size(); i++) {
			fact[i] = fact[i - 1] * i % MOD;
		}
		//逆元
		rfact[sz] = inv(fact[sz]);
		for (ll i = sz - 1; i >= 0; i--) {
			rfact[i] = rfact[i + 1] * (i + 1) % MOD;
		}
	}

	ll inv(ll x) {
		//modpow
		return pow(x, MOD - 2);
	}
	ll pow(ll x, ll n) {
		//累乗
		ll ret = 1;
		while (n > 0) {
			if (n & 1) (ret *= x) %= MOD;
			(x *= x) %= MOD;
			n >>= 1;
		}
		return (ret);
	}
	ll P(ll n, ll r) {
		//順列
		if (r < 0 || n < r) return (0);
		return (fact[n] * rfact[n - r] % MOD);
	}

	ll C(ll p, ll q) {
		//組み合わせ
		if (q < 0 || p < q) return (0);
		return (fact[p] * rfact[q] % MOD * rfact[p - q] % MOD);
	}

	ll H(ll n, ll r) {
		//重複組み合わせ
		if (n < 0 || r < 0) return (0);
		return (r == 0 ? 1 : C(n + r - 1, r));
	}
};


/******************************************************************************************/



int main() {

	ll n, k;
	cin >> n >> k;
	ll red = n - k;
	ll inside = k - 1;

	Combination comb(2050);


	for (ll i = 1; i <= k; i++)
	{
		cout << comb.C(k - 1, i - 1)*comb.C(n - k + 1, i) % MOD << endl;

	}

	return 0;
}