ARC067 - E Grouping

E - Grouping

問題概要

N 人をグループ分けします。
一つのグループにつき A ~ B 人で構成し、
同じ人数のグループは 0 か C ~ D 個作らなければいけません。
このようなグループ分けは何通りありますか。

DPの解説

DPテーブルを書いてみます。

横軸が、グループ分けしていない、残っている人の数。
縦軸が、i 人以下のグループのみでグループ分けしていることを表します。

dp[i][j] = i 人以下のグループのみにでグループ分けした時、グループ分けされていない人の数が j 人の時の通り数

入力は、3 1 2 1 2 だとします。

まず、0 人以下のグループのみでグループ分けした場合を考えます。
「誰も選べない」の 1 通りしかないので、dp[0][n] = 1。
残りの人数を減らせないので、その他はすべて0。

次に、1 人のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、1 人グループを 1 個作った場合、3 人のうちから 1 人選ぶので、 。

残り 3 人いるときに、1 人グループを 2 個作った場合、3 人のうちから 1 人選んで、 2 人のうちから 1 人選ぶ。
そして、重複を消せばよいので、 。

同じグループは 3 個以上作れないので、次に進みます。
残り2 人いるときに、1 人グループを 1 個作った場合……ですが、
dp[0][2] = 0 のため、dp[1][1] += となります。
計算をしても +0 するだけなので省略。

これで 1 人グループを作る場合をすべて試せました。
この計算結果は、1 人グループのみでグループ分けした結果の通り数を表しています。

縦軸は、i 人以下のグループのみでグループ分けしていることを表すので、0 行の結果を加える必要があります。

次に、2 人以下のグループのみでグループ分けした場合を考えます。
残り 3 人いるときに、2 人グループを 1 個作った場合、 。

2 人グループは 1個以上作れないので、次に進みます。
残り 2 人いるときに、2 人グループを 1 個作った場合、 。

2人グループを作る場合が終わりました。

あとは先と同様に、1行の結果を加えます。

これで本当に正しいのか、組み合わせを列挙してみます。

残り 3 人のとき
{} (空集合)
より 1 通り。

残り 2 人のとき
{1}
{2}
{3}
より 3 通り。

残り 1 人のとき
{1, 2}
{1, 3}
{2, 3}
{ {1}, {2} }
{ {1}, {3} }
{ {2}, {3} }
より 6 通り。

残り 0 人のとき
{ {1, 2}, {3} }
{ {1, 3}, {2} }
{ {2, 3}, {1} }
より 3 通り。

どうやら正しいようです。

実装

先に組み合わせ、階乗の逆元を計算しておきます。
あとは遷移させます。

計算結果がどんどん加算されていくDPなので、更新する方向に気をつければ 1 次元配列で計算できます。

残り 1000 人を 1 人グループに分ける場合、
1 個のとき：
2 個のとき：
3 個のとき：
....
と組み合わせの計算に時間がかかるので、前回の計算結果を用いて計算量を落としています。

#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

const long long M = 1000000007;

long long nCr[1005][1005];
void Pascals(){
	nCr[0][0] = 1;
	range(i,1,1001){
		rep(j,i + 1){
			if(j == 0) nCr[i][j] = nCr[i - 1][j];
			else if(j == i) nCr[i][j] = nCr[i - 1][j - 1];
			else nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]);
			nCr[i][j] %= M;
		}
	}
}

//べき乗 x^n mod M
long long power(long long x, long long n){
	long long res = 1;
	if(n > 0){
		res = power(x, n / 2);
		if(n % 2 == 0) res = (res * res) % M;
		else res = (((res * res) % M) * x ) % M;
	}
	return res;
}

//階乗
long long fact[1005];
long long factorial(long long n, long long r){
	long long res = 1;
	range(i,r,n + 1){
		res*= i;
		res%= M;
		fact[i] = res;
	}
	return res;
}

int main(){
	Pascals();
	factorial(1000,1);
	long long fact_rev[1005];
	rep(i,1001) fact_rev[i] = power(fact[i], M - 2);

	long long n, a, b, c, d;
	cin >> n >> a >> b >> c >> d;

	long long dp[1005] = {0};
	dp[n] = 1;
	range(i,a,b + 1){
		range(k,i * c,n + 1){
			long long person = k;
			long long comb = 1;

			range(j,1,d + 1){
				long long join = i * j;
				if(k - join < 0) break;

				(comb *= nCr[person][i]) %= M;
				person-=i;

				if(j >= c){
					(dp[k - join] += dp[k] * comb % M * fact_rev[j] % M) %= M;
				}
			}
		}
	}

	cout << dp[0] << endl;
}