https://www.acmicpc.net/problem/25028
#25028: 완전 생성
![[ 백준 2225번 ] 합분해](https://full.eternals.kr/wp-content/plugins/contextual-related-posts/default.png "[ 백준 2225번 ] 합분해")
양의 정수만 있는 단조롭게 증가하는 시퀀스 $G$가 있습니다.
이 시퀀스에서 $G_i$는 $i$가 $1$보다 크거나 같은 정수이고 $i$가 $G$에서 발생하는 횟수를 나타내는 경우 정의됩니다.
정확히 말하면 $G$는 $i$가 $G_i$번 발생하는 것입니다.
www.acmicpc.net
이것은 설명하기가 매우 어려운 문제라고 생각합니다.
우선 글에 있는 sequence를 Golomb sequence 등이라고 하며 Wikipedia와 OEIS에 문서가 있습니다.
물론 가장 간단한 해결책은 모든 $G_{i}$를 찾는 것입니다.
이는 추가와 같은 메서드를 지원하는 컨테이너로 쉽게 구현할 수 있지만 공간 복잡도가 $O(n)$이므로 사용할 수 없는 솔루션이 됩니다.
따라서 적어도 이것보다 더 나은 해결책을 찾아야 합니다.
Golomb 시퀀스의 값이 매우 반복적이므로,
$$\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 \ 곱하기 x^{G_{x}} \times \cdots$$
그렇게 하면 $G_{n}$까지만 곱한 값을 얻을 수 있습니다.
이 접근 방식으로 포스를 몇 번 호출해야 하는지 봅시다.
$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})$(보다 정확한 근사는 나중에 설명함)처럼 보이고, 이 근사를 취하면 $\sum_{i=1}^{k} G_ { i} \ 대략 O(k \sqrt{k})$ 이므로 거듭제곱 함수에 대한 호출 수는 $O(n^{\frac{2}{3}})$ 입니다.
지수화 함수의 복잡도는 대수적이지만 이 호출 수로는 어떤 슬라이스도 $10^{12}$의 0.5초 안에 $n$를 처리할 수 없습니다.
하위 작업 2를 해결하는 더 빠른 접근 방식을 고려해 보겠습니다.
위의 접근 방식은 반복되는 $G_{i}$ 값을 그룹화하여 빠르게 계산하는 것이지만 더 빠르게 하려면 더 큰 그룹으로 그룹화하고 관찰해야 합니다.
이를 위해 무한 시퀀스 $G_{i}$에 대해 f(G_{i})$ 각 $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 | 에프(엑스) = k \오른쪽 \} $$
$$ T_{k} = \left \{ x | G_{x} \in S_{k} \right \} $$
작은 숫자를 입력한 예입니다.
$$ S_{4} = \왼쪽 \{ 6,7,8 \오른쪽 \} $$
$$ T_{4} = \왼쪽 \{ 12,13,14, \cdots, 21,22,23 \오른쪽 \} $$
이제 $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}$$
즉, $T_{k}$ 요소의 최대값을 찾는 방법이 필요합니다.
예를 들어 $\mathrm{max} (T_{k})$라고 합시다.
이 시점에서 $T_{k}$ $|T_{k}| = k \times G_{k}$. 그러므로,
$$\mathrm{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} (즉 \times G_{i})$$
보지마. 이 $k$는 빠르게 찾을 수 있으며 실제로는 $k \leq 300$ in $n \approx 10^{6}$입니다.
이제 $n \in T_{k}$인 $k$의 값을 찾았으므로 정답을 찾았습니다.
우선, 정의상
$$\prod_{i=1}^{\mathrm{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}^{ \mathrm{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}$ $
이제 아직 곱하지 않은 숫자를 고려하십시오.
나머지 숫자의 곱은 $\mathrm{min} (S_{k})$에서 $G_{n}-1$까지 $k$번, $G_{n}$에 $k$번 또는 $를 곱합니다.
\ 왼쪽 ( \ 곱하기 왼쪽 ( n – \textrm{max} (T_{k-1}) \right ) \; \% \; k \right )$ 번. 예를 들어 $n=19$, $k=4$이고 $\mathrm{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 )^{\text{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 브래킷을 소개할 때 다음과 같습니다.
$$\mathrm{power}(n,k) = ( k | \left ( n – \mathrm{max} (T_{k-1}) \right ) ) \times k + \left ( (n – \mathrm {max}(T_{k-1})) \; \% \; k \right )$$
$G_{n}$를 자세히 관찰하면
$$G_{n} = ( k | (n – \mathrm{max} (T_{k-1})) ) \times (\sum _{i=1}^{k-1} G_{i} + \ lfloor \frac{n – \mathrm{max} (T_{k-1}) }{k} \rfloor ) + ( k \nmid (n – \mathrm{max} (T_{k-1})) ) ) \ 시간 (1 + \sum_{i=1}^{k-1} G_{i} + \lfloor \frac{n – \text{max} (T_{k-1}) }{k} \rfloor ) $ $
아이버슨 대괄호 때문에 장황해 보일 수 있지만, 경우의 수를 생각해보면,
$$\left ( G_{n} \right ) ^{\mathrm{power}(n,k)} = \left ( 1 + \sum_{i=1}^{k-1} G_{i} + \ lfloor \frac{n – \mathrm{max} (T_{k-1}) }{k} \rfloor \right )^{((n – \mathrm{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 – \text{max} (T_{k-1}) }{k} \rfloor + \sum_{i=1}^{k-1} G_{i} \right )^{ ( ( n – \mathrm{max} (T_{k-1}) ) \; \% \; k ) } \ 곱하기 \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} \ 왼쪽 ( \prod_{j = 1 + \sum_{l=1}^{i-1} G_{l}}^{\sum_{l=1}^{i} G_{l}} j \right )^ {i}$$
마지막으로 할 일은 $G_{i}$를 빨리 찾는 것입니다.
(물론 하위 작업 2에서 제시한 $G_{i}$를 빠르게 얻기 위한 위에서 설명한 간단한 접근 방식은 존재하지 않습니다.
)
유도 과정을 생략하면 $G_{n}$에 대해 다음과 같은 재귀 방정식이 성립함을 알 수 있습니다.
$$G_{n+1} = 1 + G_{ (n+1 – G_{G_{n}} ) }$$
이 재귀 공식을 사용하면 $G_{n}$는 $O(n)$에서 공간 및 시간 복잡성 모두에 대해 얻을 수 있습니다.
또한 $G_{n}$에 대한 점근식은 다음과 같다는 것을 알고 있습니다.
$$G_{n} = \phi ^{2 – \phi} \times n^{\phi – 1}$$
이때 정답을 찾기 위한 시간복잡도를 계산해 보자.
우선 $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}$까지 계산해야 하며 이는 위의 반복과 동일합니다.
$\sum_{i=1}^{k} G_{i}$의 값은 동일한 복잡성으로 계산될 수 있습니다.
복잡성에 추가로 영향을 미치는 것은 거듭제곱 함수에 대한 호출이며, $O(k)$ 호출이 있으므로 거듭제곱 계산의 복잡성은 $O(k\log k)$가 됩니다.
그러면 문제 해결의 시간 복잡도는 $O(k \log k)$이고 $k$의 근사치를 사용하면 $O(n^{-(1 + \phi)} \log n) $가 됩니다.
$n$을 $10^{12}$로 바꾸면 이 복잡도를 0.5초 이내에 쉽게 실행할 수 있다고 가정할 수 있습니다.
한편, 공간 복잡도는 $O(k)$, 즉 $O(n^{-(1 + φ)}$)이며, 이 역시 메모리 한계를 충분히 초과함을 알 수 있다.
실제로 $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)
문제를 해결하기 위해 다음을 사용했습니다.
Golomb 시퀀스의 반복 관계가 왜 그렇게 중첩되어 있는지 아직 잘 모르겠지만 아래 링크가 도움이 될 수 있습니다.
여담으로 S. Golomb은 이 분야에서 활발한 연구를 해온 것으로 보여 Golomb의 염기서열이 여러 개 있어 자료를 찾기 어렵다.
이렇게 해도 $n$이 10$^{15}$를 넘어서면 $k$는 매우 커집니다.
$n$을 $10^{18}$로 늘려서 답을 얻을 수 있다면 재미있겠지만 $f(G)$가 Golomb의 시퀀스 자체로 나타나는지, 함수를 다시 신청하세요… 복잡해지는 것 같네요… 다른 방법은 없나요?