[BOJ] 14949 - 외계 미생물

https://www.acmicpc.net/problem/14949

BOJ - 외계 미생물

문제 유형: 수학, 조합론, 정수론, 다이나믹 프로그래밍

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 256MB

 

문제

항상 B, C가 가득 찬 성적표를 보고 자신이 컴퓨터 공학에 크게 재능이 없다고 생각한 윤영이는 결국 전공을 바꾸어 항공우주학과와 생물학과를 복수전공 하였고, 외계 생물 연구가로 큰 성공을 거두었다.

그러던 중 어떤 행성에서 특이한 외계 미생물을 발견하게 되었고, 이를 신기하게 생각했던 윤영이는 몇 마리를 자신의 연구소로 가지고 왔다. 연구 결과 미생물은 다음과 같은 특징을 가지고 있음을 확인할 수 있었다.

1. 미생물은 스스로 자식을 낳으며, 하루동안 모든 자식을 낳고 죽는다. 낳을 수 있는 자식의 수는 미생물이 자유롭게 정할 수 있다. 또한, 자식은 낳은 순서에 따라 구분된다. 자식은 태어난 다음날부터 새로운 자식을 낳을 수 있다.
2. 미생물은 자식 간의 지나친 경쟁이 생기는 것을 원하지 않는다. 그래서 현재 존재하는 미생물들이 낳은 자식의 수의 총 합이 일정 수 W이하가 되도록 서로 협력한다. (W는 세대가 변해도 일정하다고 가정한다.)
3. 각 미생물은 자식을 안 낳을 수도 있지만, 종족 유지를 위해 모든 미생물이 자식을 낳지 않는 경우는 생기지 않게 한다. (단, 자식을 낳지 않더라도 자신이 태어난 다음날 죽는다.)

윤영이는 이 생물이 번식하는 양상을 재미있어 했고, 미생물 한 마리만 자신의 실험실에 가지고 와서 용기에 담아뒀다. 미생물은 자신이 존재하는 용기에서 (2)번 조건에서 말한 지나친 경쟁이 발생하지 않을 수 있는 최대 자식의 수의 합은 W라고 생각했고, 번식을 시작했다. H일 동안 생길 수 있는 번식 양상의 경우의 수를 구하시오.

 

입력

첫째 줄에 H와 W가 주어진다. 0 ≤ H ≤ 5, 1 ≤ W ≤ 200 이다.

 

출력

생물이 H일이 지나는 동안 번식 할 수 있는 양상의 개수를 출력하시오. 경우의 수가 너무 커질 수 있기 때문에 1,000,000,007로 나눈 나머지를 출력하라. 계산 과정에서 32비트 정수 변수가 표현할 수 있는 범위를 넘어서 64비트 정수 변수 (long long)를 사용해야 할 수도 있음에 주의하라.

 

풀이

dp[흐른 시간][남은 생물 수] = 경우의 수로 한다.

dp[0][1] = 1로 시작할 수 있다.

 

그 뒤로, 1 <= days <= H, 1 <= i, j <= W 에 대해, 이전 i마리 생물이 이번에 j마리 생물이 된다고 가정하면, 점화식은 다음과 같다:

 

(i+j-1)C(j)는 i개의 생물이 각자 0마리 이상의 총합 j마리 자식을 낳는 경우의 수이다.

이를 별과 막대 공식(stars and bars)이라고 하는데,

정수의 합을 만족하는 음이 아닌 정수 조합의 개수를 세는 방법이다.

n개의 별이 일렬로 있을 때, k개의 그룹으로 나눈다고 해보자.

그러면, k-1개의 막대를 설치해야 한다.

그러면 총 n+k-1개의 요소가 나열되고, 이 중에서 k-1개를 뽑아서 그것들을 막대로, 나머지를 별로 간주한다고 생각하면, 

(n+k-1)C(k-1)이 된다.

 

위에서는 (prev+curr-1)C(curr)이라고 해놓은 것인데, 이는 이전 부모 prev마리들에게 낳을 수 있는 자식의 수 curr마리를 분배한 것이라고 생각하면 된다. 대신, curr >= 1 을 전제로 하여 모두가 0인 경우는 제외되었다.

 

그리고, 페르마 소정리와 분할 정복 거듭제곱을 이용해서 빠르게 합동인 조합 수를 구한다.

 

 

그 뒤, 모든 dp[h]의 합을 MOD로 나눈 것을 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int h, w;
const int MOD = 1e9 + 7;

ll fact[401], invFact[401];

ll bpow(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp % 2) {
            res = (res * base) % MOD;
        }
        exp >>= 1;
        base = (base * base) % MOD;
    }
    return res;
}

ll nCr(ll n, ll r) {
    return ((fact[n] * invFact[r]) % MOD) * invFact[n - r] % MOD;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i <= 400; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    for (int i = 0; i <= 400; i++) {
        invFact[i] = bpow(fact[i], MOD - 2);
    }
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> h >> w;

    precompute();
    vector<vector<int>> dp(h + 1, vector<int>(w + 1, 0));
    dp[0][1] = 1;

    for (int day = 1; day <= h; day++) {
        for (int i = 1; i <= w; i++) {
            if (dp[day - 1][i] == 0) continue;
            for (int j = 1; j <= w; j++) {
                dp[day][j] =
                    (dp[day][j] + (dp[day - 1][i] * nCr(i + j - 1, i-1))) % MOD;
            }
        }
    }

    ll ans = 0;
    for (int i = 1; i <= w; i++) {
        ans = (ans + dp[h][i]) % MOD;
    }

    cout << ans << "\n";

    return 0;
}