はまやんはまやんはまやん

hamayanhamayan's blog

ロジックパズルの組み合わせ [yukicoder 389]

問題

http://yukicoder.me/problems/no/389

1行M列のマスがある。
これを(空白)(H1連続で塗る)(空白)(H2連続で塗る)...(空白)(Hk連続で塗る)(空白)と塗る。
要はイラストロジックみたいに塗る。
この塗り方を数えて、10^9+7で割った余りを答える。

k==1でHi==0の時に限り、1通りとする。
入力された塗り方が存在しないならNAを出力。

1 <= M <= 10^6

考察

1. 組合せを数える系はいろんな解法があるが、まずは数学的に求められないか(俺は)考える
2. もっともっとよく考えるとできると気づく

サンプル1 M=10, k=2, H={7,1} で考える。

1. まず連続で塗る所の間は最低1つ空白が必要なので、必要最小限の構成を作る
■■■■■■■□■

2. 空白が余るので、この空白の割り当て方を考える。今回の例であれば、1つの空白が余る
空白が入れられる部分が最左と最右と各塗られている所の間の3つある。
異なる3つのスペースに重複を許して1つの空白を分け与える組合せ -> 重複組合せ 1H3

3. 一般化する

Mマスでヒントがk個、ヒントで塗られるマスの総和をsumとする。

1. 最小限の構成に必要なマスの数は、sum + k - 1マス
与えられているマスがこのマス未満であれば、塗り方が存在しないためNA

2. 余っている空白はM-(sum + k - 1)マスで、空白を入れられるスペースはk+1個 -> 重複組合せ (M-(sum+k-1))H(k+1)

4. 重複組合せは組合せで計算可能 aHb = (a+b-1)C(b-1)

実装

http://yukicoder.me/submissions/102381

typedef long long ll;
ll MOD = 1000000007;
const int NUM_FAC = 2000001;
ll modfact(ll x) {
	static ll _fact[NUM_FAC + 1];
	if (_fact[0] == 0) {
		_fact[0] = 1;
		for (int i = 1; i <= NUM_FAC; ++i) _fact[i] = _fact[i - 1] * i%MOD;
	}
	return _fact[x];
}
ll modpow(ll a, ll n) {
	ll r = 1;
	while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1;
	return r;
}
ll moddiv(ll a, ll b)
{
	ll ap_2 = modpow(b, MOD - 2);
	return (a * ap_2) % MOD;
}
ll aCb(ll a, ll b) {
	return moddiv(modfact(a), (modfact(a-b) * modfact(b))% MOD);
}
ll nHk(ll n, ll k)
{
	return aCb(n + k - 1, k - 1);
}
//-----------------------------------------------------------------
int M;
vector<int> H;
//-----------------------------------------------------------------
int main() {
	cin >> M;

	int x;
	while (cin >> x) H.push_back(x);

	if (H.size() == 1 && H[0] == 0) {
		printf("1\n");
		return 0;
	}

	int sum = 0;
	rep(i, 0, H.size()) sum += H[i];
	int a = M - sum - (H.size() - 1);
	int b = H.size() + 1;

	if (a < 0) {
		cout << "NA" << endl;
		return 0;
	}

	ll ans = nHk(a, b);
	cout << ans << endl;
}