백준 25028번: Fully Generate

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

25028번: Fully Generate

---

풀이를 설명하기가 상당히 난해한 문제라고 생각합니다. 우선, 글에 나오는 수열은 Golomb Sequence 등으로 불리며 Wikipedia, OEIS에 문서가 있습니다.

---

가장 단순한 풀이는 물론 $G_{i}$를 모두 구하는 것입니다. 이는 append같은 메서드를 지원하는 컨테이너를 써서 쉽게 구현할 수 있는데, space complexity가 $O(n)$인 만큼 쓸 수 없는 풀이가 되겠습니다. 따라서, 적어도 이것보다는 더 나은 풀이를 구상해야 합니다.

---

Golomb Sequence의 값들은 굉장히 repetitive하므로, 문제에서 구해야 하는 값인

$$\prod_{i=1}^{n} G_{i}$$

에서 각각의 자연수 $x$가 몇 번 등장하는 지를 세면 계산량이 줄어들 것을 기대할 수 있습니다. 즉,

$$\prod_{i=1}^{\infty} G_{i} = 1^{1} \times 2^{2} \times 3^{2} \times 4^{3} \times \cdots \times x^{G_{x}} \times \cdots$$

와 같이 나타낸 뒤에, $G_{n}$까지만 곱한 값을 얻어냅니다.

 

이 접근에서 거듭제곱을 몇 회 호출해야하는지 알아보겠습니다. 문제의 input $n$에 대해

$$\sum_{i=1}^{k} G_{i} < n \leq \sum_{i=1}^{k+1} G_{i}$$

가 성립하는 자연수 $k$를 가정했을 때, 거듭제곱 함수를 $k+1$번 호출하게 됩니다.

 

대략 $G_{k} \approx O(\sqrt{k})$ 같이 보이고, (보다 정확한 approximation은 후술하겠습니다) 이런 근사를 취했을 때 $\sum_{i=1}^{k} G_{i} \approx O(k \sqrt{k})$ 이므로 거듭제곱 함수의 호출 횟수는 $O(n^{\frac{2}{3}})$ 입니다.

 

거듭제곱 함수의 복잡도가 로그 스케일이지만, 이정도 호출 횟수에서는 아무리 커팅을 해도 $n$이 $10^{12}$ 정도로 클 때를 0.5초 안에 처리할 수 없습니다. 서브 태스크 2를 해결하기 위해 더 빠른 접근을 생각합시다.

---

위 접근은 반복되는 $G_{i}$ 값끼리 묶어 빠르게 계산하자는 것인데, 이보다 더 빨라지기 위해서는 더 큰 그룹으로 묶어 관찰할 수밖에 없을 것입니다. 이를 위해서, 무한한 수열 $G_{i}$에 대해, 각 $G_{i}$ 값이 반복되는 횟수 $f(G_{i})$를 정의한다면, $f(G_{i})$ 마저도 반복되는 것을 알 수 있는데, 이 반복되는 $f(G)$ 값들을 묶어줍니다.

 

아래를 참고하면 이해가 빠를 것입니다.

$$G_{1} = 1 \rightarrow f(1) = 1$$

$$G_{2} = G_{3} = 2 \rightarrow f(2) = 2$$

$$G_{4} = G_{5} = 3 \rightarrow f(3) = 2$$

$$G_{6} = \cdots = \ G_{8} = 4 \rightarrow f(4) = 3$$

$$G_{9} = \cdots = \ G_{11} = 5 \rightarrow f(5) = 3$$

$$G_{12} = \cdots = \ G_{15} = 6 \rightarrow f(6) = 4$$

$$G_{16} = \cdots = \ G_{19} = 7 \rightarrow f(7) = 4$$

$$G_{20} = \cdots = \ G_{23} = 8 \rightarrow f(8) = 4$$

여기서 두 집합 $S$, $T$를 다음과 같이 정의합니다.

$$S_{k} = \left \{ x | f(x) = k \right \}$$

$$T_{k} = \left \{ x | f(G_{x}) = k \right \}$$

작은 숫자를 넣었을 때의 예시입니다.

$$S_{4} = \left \{ 6,7,8 \right \}$$

$$T_{4} = \left \{ 12,13,14, \cdots, 21,22,23 \right \}$$

이제 $n \in T_{k}$인 $k$의 값을 구하면 문제의 답을 얻을 수 있습니다. 먼저 그 $k$ 값을 구하는 방법을 보여드리겠습니다.

 

정의에 따라

$$i \ne j \leftrightarrow T_{i} \cap T_{j} = \varnothing$$

이므로, $T_{i}$의 원소들의 범위를 살펴보면 됩니다.

 

쉬운 예시는 다음과 같습니다.

 

$18 \in T_{4}$를 다음과 같이 구합니다.

 

$$(x \in T_{3} \rightarrow 6 \leq x \leq 11) \rightarrow 18 \not\in T_{3}$$

$$(x \in T_{4} \rightarrow 12 \leq x \leq 23) \rightarrow 18 \in T_{4}$$

 

즉 $k$ 값을 구하기 위해서는, $T_{k}$의 원소의 최댓값, 이를테면 $\textrm{max} (T_{k})$를 구하는 방법이 필요합니다.

 

이때 관찰을 통해 집합 $T_{k}$의 크기 $|T_{k}| = k \times G_{k}$임을 알 수 있습니다. 따라서,

$$\textrm{max} (T_{k}) = \sum_{i=1}^{k} (i \times G_{i})$$

입니다.

 

따라서,

$$n \in T_{k} \rightarrow \sum_{i=1}^{k-1} (i \times G_{i}) < n \leq \sum_{i=1}^{k} (i \times G_{i})$$

입니다. 이런 $k$를 빠르게 구할 수 있는데, 실제로 $n \approx 10^{6}$에서 $k \leq 300$입니다.

---

이제 $n \in T_{k}$인 $k$값을 찾았으니, 정답을 구합니다. 제일 먼저, 정의에 의해

$$\prod_{i=1}^{\textrm{max} (T_{k-1}) } G_{i} = \prod_{i=1}^{k-1} \left ( \prod_{j \in S_{i}} j^{i} \right ) = \prod_{i=1}^{k-1} \left ( \prod_{j \in S_{i}} j \right )^{i}$$

입니다. 그런데 관찰을 통해 다음을 알 수 있습니다.

$$x \in S_{k} \rightarrow \sum_{k=1}^{k-1} G_{i} < x \leq \sum_{i=1}^{k} G_{i}$$

이를 활용하면 다음과 같은 식을 얻습니다.

$$\prod_{i=1}^{ \textrm{max} (T_{k-1}) } G_{i} = \prod_{i=1}^{k-1} \left ( \prod_{j = 1 + \sum_{l=1}^{i-1} G_{l}}^{\sum_{l=1}^{i} G_{l}} j \right )^{i}$$

이제 아직 곱해주지 않은 숫자들을 관찰합니다.

 

나머지 숫자들의 곱은 $\textrm{min} (S_{k})$부터 $G_{n}-1$까지 $k$번 곱하고, $G_{n}$을 $k$번 또는 $\left ( \left ( n - \textrm{max} (T_{k-1}) \right ) \; \% \; k \right )$번 곱한 것입니다. 예시를 들어 설명하자면, $n=19$일 때 $k=4$이며 $\textrm{max}(T_{3}) = 11$에서 $k$씩 커졌을 때 $n$에 도달하기 때문에 $G_{n}$이 전체 곱에서 $k$번 등장합니다. $n=22$이라면 $G_{n}$이 3번 등장하는데, $\left ( \left ( n - \textrm{max} (T_{k-1}) \right ) \right ) = 11$ 개의 숫자를 $k$개씩 쪼갰을 때 나머지가 3입니다.

 

여기까지가 다음 식과 같습니다.

$$\prod_{i=1}^{ n } G_{i} = \left ( G_{n} \right )^{\textrm{power}(n,k)} \times \left ( \prod_{i = 1 + \sum_{j=1}^{k-1} G_{i}}^{G_{n} - 1} i \right )^{k} \times \prod_{i=1}^{k-1} \left ( \prod_{j = 1 + \sum_{l=1}^{i-1} G_{l}}^{\sum_{l=1}^{i} G_{l}} j \right )^{i}$$

$\textrm{power}(n,k)$는 Iverson bracket을 도입했을 때 다음과 같습니다.

$$\textrm{power}(n,k) = [ k | \left ( n - \textrm{max} (T_{k-1}) \right ) ] \times k + \left ( (n - \textrm{max}(T_{k-1})) \; \% \; k \right )$$

 

$G_{n}$을 잘 관찰해보면 다음과 같습니다.

$$G_{n} = [ k | (n - \textrm{max} (T_{k-1})) ] \times (\sum_{i=1}^{k-1} G_{i} + \lfloor \frac{n - \textrm{max} (T_{k-1}) }{k} \rfloor ) + [ k \nmid (n - \textrm{max} (T_{k-1})) ] \times (1 + \sum_{i=1}^{k-1} G_{i} + \lfloor \frac{n - \textrm{max} (T_{k-1}) }{k} \rfloor )$$

Iverson bracket 때문에 장황해보일 수 있지만, 경우의 수를 나눠 생각해보면 결국

$$\left ( G_{n} \right ) ^{\textrm{power}(n,k)} = \left ( 1 + \sum_{i=1}^{k-1} G_{i} + \lfloor \frac{n - \textrm{max} (T_{k-1}) }{k} \rfloor \right )^{((n - \textrm{max} (T_{k-1} ) ) \; \% \; k ) } \times \left ( \sum_{i=1}^{k-1} G_{i} + \lfloor \frac{n - \textrm{max} (T_{k-1})}{k} \rfloor \right )^{k}$$

이므로, 식이 다음과 같이 정리됩니다.

$$\prod_{i=1}^{ n } G_{i} = \left ( 1 + \lfloor \frac{ n - \textrm{max} (T_{k-1}) }{k} \rfloor + \sum_{i=1}^{k-1} G_{i} \right )^{ ( ( n - \textrm{max} (T_{k-1}) ) \; \% \; k ) } \times \left ( \prod_{i = 1 + \sum_{j=1}^{k-1} G_{j}}^{\lfloor \frac{ n - \textrm{max}(T_{k-1}) }{k} \rfloor + \sum_{j=1}^{k-1} G_{j}} i \right )^{k} \times \prod_{i=1}^{k-1} \left ( \prod_{j = 1 + \sum_{l=1}^{i-1} G_{l}}^{\sum_{l=1}^{i} G_{l}} j \right )^{i}$$

---

이제 마지막으로 남은 건 $G_{i}$를 빠르게 구할 수 있는가입니다. (물론, 글에서 소개하는 빠르게 $G_{i}$를 구하는 방법을 위에서 말한 쉬운 접근들은 서브태스크 2를 통과하지 않습니다.)

 

유도과정을 생략하고, $G_{n}$에 대해 다음 점화식이 성립한다고 알려져있습니다.

$$G_{n+1} = 1 + G_{ (n+1 - G_{G_{n}} ) }$$

이 점화식을 사용하여 space/time complexity 모두 $O(n)$에 $G_{n}$값을 구할 수 있습니다.

 

또한, $G_{n}$에 대해 asymptotic expression이 다음과 같다고 알려져있습니다.

$$G_{n} = \phi ^{2 - \phi} \times n^{\phi - 1}$$

---

이때 정답을 구하는 time complexity는 어느정도일지 계산해보겠습니다.

 

우선, $n$에 대한 $k$값인데,

$$\sum_{i=1}^{k-1} (i \times G_{i}) < n \leq \sum_{i=1}^{k} (i \times G_{i})$$

을 만족하는 값이므로 $n \approx O(k^{\phi + 1}) \rightarrow k \approx O(n^{-(1 + \phi)})$ 입니다.

 

이때 $\sum_{i=1}^{k} (i \times G_{i})$의 계산은 $G_{1}$부터 $G_{k}$까지의 계산을 요구하며 이는 위 recurrence relation에 의해 $O(k)$에 계산할 수 있습니다. 동시에 $\sum_{i=1}^{k} G_{i}$의 값도 같은 복잡도로 계산할 수 있습니다. 그러므로 복잡도에 추가적으로 영향을 주는 것은 거듭제곱 함수의 호출이며, $O(k)$번의 호출이 있기 때문에 거듭제곱을 계산하는 데에 $O(k\log k)$라는 complexity가 나옵니다.

 

그렇다면, 문제의 답을 구하는 time complexity는 $O(k \log k)$가 되며 $k$의 approximation을 대입하면 $O(n^{-(1 + \phi)} \log n)$ 입니다. $n$에 $10^{12}$를 대입해보면, 이 complexity가 0.5초 내에 충분히 돌아갈 것으로 짐작할 수 있습니다. 한편, space complexity는 $O(k)$이고 다른 표현으로 $O(n^{-(1 + \phi)})$ 이며, 이 역시 메모리 제한을 충분히 통과함을 알 수 있습니다. 실제로, $n=10^{12}$일 때 $k=51619$입니다.

 

제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007
typedef unsigned long long ull;

ull power_modular (ull X, ull Y);

int main() {
	ull g[100001], ig[100001], sg[100001];
	
	ull N;
	scanf("%llu", &N);

    g[1] = ig[1] = sg[1] = 1;

    int L;
    for (L = 2;;L++) {
        g[L] = 1 + g[L - g[g[L-1]]];
        ig[L] = ig[L-1] + L * g[L];
        sg[L] = sg[L-1] + g[L];
        if (ig[L] >= N) {
        	break;
        }
    }
    
    ull ans = 1;
    
    ull base = 1;
    for (int i = 2; i < L; i++) {
    	base = 1;
    	for (int j = sg[i-1] + 1; j <= sg[i]; j++) {
    		base = base * j % mod;
    	}
    	ans = ans * power_modular(base, i) % mod;
    }
    
    base = 1;
    for (int i = sg[L-1] + 1; i <= sg[L-1] + (N - ig[L-1]) / L; i++) {
    	base = base * i % mod;
    }
    ans = ans * power_modular(base, L) % mod;
    
    base = sg[L-1] + (N - ig[L-1]) / L + 1;
    ans = ans * power_modular(base, (N - ig[L-1]) % L) % mod;
    printf("%llu", ans);
   
    return 0;
}

ull power_modular (ull X, ull Y) {
	ull result = 1;
	while (Y) {
		if (Y % 2) {
			result = result * X % mod;
		}
		X = X * X % mod;
		Y /= 2;
	}
	return result;
}

(C11, 120ms, 3340KB, 제출번호 57212491)

---

문제를 푸는데 다음을 참고했습니다.

• Wikipedia
• OEIS
• StackOverflow

저는 아직 Golomb's sequence의 recurrence relation이 왜 저렇게 nested한지 잘 모르겠지만, 아마 다음 링크가 도움을 줄 수 있을 듯합니다.

• Arxiv

그런데, S. Golomb이 이 방면에서 활발한 연구자였는지 Golomb의 sequence가 여러개 있어 자료를 찾기가 힘듭니다 ㅜㅜ 혹시 이 문제에서 다루는 수열에 대한 자료가 있으면 링크 부탁드립니다.

---

이런 방법으로도 $n$이 $10^{15}$ 이상으로 커지게 되면 $k$가 매우 커지게 됩니다. $n$을 $10^{18}$까지 늘려도 답을 구할 수 있다면 재밌을 것 같은데, $f(G)$가 $G$ 그 자체로 나타나는 것에 착안하여, $f(f(G))$를 기반으로 생각하면 어떨까 싶지만, 너무 복잡해지는 듯 합니다... 다른 방법이 있을까요?