https://www.acmicpc.net/problem/13912
요약
외계 생물은 태어난 지 하루가 지나면 두 마리의 새끼를 낳는다. 한 번 새끼를 낳으면 그 이후에는 추가로 새끼를 낳지 않는다. 발견한 지 0일째에는 1마리, 1일째에는 1 + 2 = 3마리, H일째에는 $2^{H+1} -1$ 마리가 된다. H일째에 이 외계 생물들에게 번호를 붙이고자 한다. 부모의 번호를 자식의 번호보다 항상 작게 하려고 할 때, 번호를 붙이는 경우의 수를 출력한다.
1. 0일 차에 발견된 외계 생물은 항상 1번을 부여받는다. 외계 생물들의 관계를 이진트리로 생각한다면, 0일 차에 발견된 1번 외계 생물은 모든 외계 생물들의 조상이다.
2. 부모가 다른 외계 생물들은 서로 독립적이다. 즉, 한 부모에서 나온 두 명의 자식이 형성하는 트리는 서로에게 전혀 영향을 미치지 않는다.
3. 따라서, 문제는 1번 자리를 고정하고, 나머지 $2^{H+1} - 2$의 번호를 크기가 절반인 두 그룹으로 나누는 것과 같다. 각 그룹의 번호를 부여하는 경우는 $H - 1$일 때 번호를 부여하는 경우의 수와 같다. 우리가 구하고자 하는 값은 다음과 같은 점화식으로 표현될 수 있다.
$a_H = \binom{2^{H + 1} - 2}{2^{H} - 1}\times a_{H - 1} \times a_{H - 1}$
$2^{H+1} - 2$개의 번호 중 $2^{H} - 1$개의 번호를 택하여 번호를 부여하고, 나머지 번호들을 부여한다.
4. 우선, 점화식에서 조합 값을 사용하기 때문에, 값에 빠르게 접근하기 위하여 전처리 과정을 거쳤다. 풀이에서 원하는 값이 경우의 수를 소수 $p$로 나눈 값이므로, 페르마의 소정리을 이용, 팩토리얼 값과 팩토리얼의 곱셉의 역원의 값을 전처리하여 사용하면 시간복잡도는 $O(2^{N}logp)$이고, 이후에 값에 접근하는 것은 $O(1)$에 가능하다.
파스칼의 삼각형 방식으로 전처리를 진행한다면, $O(2^{2N})$의 시간 복잡도로 전처리를 해결할 수 있다.
이후, 점화식을 풀이하기 위해 bottom-up 방식의 DP를 사용하였고, 이는 시간복잡도 $O(N)$에 해결 가능하다.
#include <iostream>
using namespace std;
long long mod = 1000000007;
int H;
long long table[11];
long long factorial[2049];
long long ifactorial[2049];
void pre(void);
long long comb(long long N, long long K);
long long exp(int N);
int main(void) {
cin >> H;
pre(); // 전처리 과정
table[0] = 1; // 0일차에 발견된 외계생물의 번호를 부여하는 경우의 수, basecase
for (int i = 1; i <= 10; i++) table[i] = ((comb(exp(i + 1) - 2, exp(i) - 1) * table[i - 1]) % mod * table[i - 1]) % mod;
cout << table[H];
return 0;
}
void pre(void) {
factorial[0] = 1;
for (int i = 1; i <= 2048; i++) factorial[i] = (factorial[i - 1] * i) % mod;
long long exponential = factorial[2048];
long long result = 1;
int bit = 1;
while (1) {
if (bit > (mod - 2))
break;
if (bit & (mod - 2))
result = (result * exponential) % mod;
exponential = (exponential * exponential) % mod;
bit <<= 1;
}
ifactorial[2048] = result;
for (int i = 2047; i >= 0; i--) ifactorial[i] = (ifactorial[i + 1] * (i + 1)) % mod;
return;
}
long long comb(long long N, long long K) {
return ((factorial[N] * ifactorial[K]) % mod * ifactorial[N - K]) % mod;
}
long long exp(int N) {
long long result = 1;
for (int i = 0; i < N; i++)
result *= 2;
return result;
}
'풀이 포스팅 > 3팀(목요일 20:00 ~)' 카테고리의 다른 글
[백준 17833번] 홍익대학교 지하캠퍼스, C++ 풀이 (1) | 2022.11.24 |
---|---|
[백준 20046번] Road Reconstruction, C++ 풀이 (0) | 2022.11.24 |
[백준 2423번] 전구를 켜라 / Switch the Lamp On, C++ 풀이 (0) | 2022.11.24 |
[BOJ 16565번] N포커, C++ 풀이 (0) | 2022.10.07 |
[BOJ 1007번] 벡터 매칭, C++ 문제 풀이 (3) | 2022.09.29 |