26665. Iloczyny Fibonacciego를 한 줄로 요약하면 자연수의 제켄도르프 표현의 곱을 구하는 문제이다. 기존에 알려진 논문이나 다른 유저의 풀이와는 전혀 다른 풀이를 찾은 것 같아 글로 남긴다.

Preliminary: 제켄도르프 표현이란

제켄도르프의 정리는 다음과 같다.

모든 자연수는 서로 이웃하지 않은 1개 이상의 피보나치 수의 합으로 나타낼 수 있으며, 그 방법은 유일하다.

처음 몇 개의 자연수를 이 방법으로 표현하면 다음과 같다.

$$\begin{align*} 1 &= 1 \\ 2 &= 2 \\ 3 &= 3 \\ 4 &= 3 + 1 \\ 5 &= 5 \\ 6 &= 5 + 1 \\ 7 &= 5 + 2 \\ 8 &= 8 \\ 9 &= 8 + 1 \\ &\cdots \\ 32 &= 21 + 8 + 3 \\ 33 &= 21 + 8 + 3 + 1 \\ 34 &= 34 \\ &\cdots \end{align*} $$

이런 표현을 2진법과 비슷하게 1과 0으로 이루어진 문자열로도 표현할 수 있다. 이 글에서는 편의상 가장 낮은 자리부터 쓴다. 2진법도 같은 방향으로 쓰면 ($1101_2 = 1 + 2 + 8$), 다음과 같이 수식으로 풀어 쓸 수 있다.

$$\begin{align*} \overline{a_0 a_1 a_2 \cdots a_n} = \sum_{i=0}^{n}{a_i 2^i} \\ a_i \in \{0, 1\}, a_n = 1 \end{align*} $$

위의 수식에서 $2^i$를 피보나치 수열의 $i$번째 항 $F_i$로 교체하면 된다. 여기서 피보나치 수열은 $F_0 = 1, F_1 = 2$로 정의되며, 연속한 두 $a_i$가 모두 1이면 안된다는 조건이 추가된다.

$$\begin{align*} \overline{a_0 a_1 a_2 \cdots a_n} = \sum_{i=0}^{n}{a_i F_i} \\ a_i \in \{0, 1\}, a_n = 1, a_i a_{i+1} = 0 \end{align*} $$

이를 제켄도르프 표현이라고 한다. 예를 들어, $32 = 21 + 8 + 3 = F_6 + F_4 + F_2$는 $0010101$이 된다.

두 제켄도르프 표현의 합

두 제켄도르프 표현의 합을 구하는 문제도 있다. (7964. Fibonacci Sums) 가능한 경우를 잘 따져가면서 받아올림을 잘 처리하면 된다. 스포일러 방지를 위해 연습문제로 남긴다.

두 제켄도르프 표현의 곱

2020년 논문에서는 $\varphi$진법을 중간 다리로 사용하는 방법을 제시하였다. $\varphi$진법 표현은 제켄도르프 표현과 똑같이 연속한 두 자리에 1이 있을 때 다음 자리의 1 하나로 반올림할 수 있다는 특징이 있으면서, 피보나치 진법과 다르게 FFT 다항식 곱셈을 사용할 수 있다는 점을 이용한다.

sait2000님의 풀이는 자세히는 모르지만 $\varphi^2$진법을 쓴다고 전해 들었다.

반면, 본인의 풀이는 $\varphi$와는 하등 연관성이 없고, 매우 애드혹한 관찰 n개를 연달아 함으로써 convolution을 적용할 수 있는 부분을 찾아내었다.

두 피보나치 수의 곱의 전개

일단 두 제켄도르프 표현을 곱하면 $F_x F_y$의 형태의 값이 무수히 쏟아진다는 점에 주목하여, $F_x F_y$를 $F_i$들의 합으로 나타내는 방법을 찾아보았다.

$$\begin{align*} F_0 F_n &= F_n \\ F_1 F_n &= 2 F_n = F_{n-2} + F_{n+1} \\ F_2 F_n &= 3 F_n = F_{n-2} + F_{n+2} \\ F_3 F_n &= 5 F_n = F_{n-4} + F_{n-1} + F_{n+3} \\ F_4 F_n &= 8 F_n = F_{n-4} + F_{n} + F_{n+4} \\ &\cdots \\ F_8 F_n &= F_{n-8} + F_{n-4} + F_{n} + F_{n+4} + F_{n+8} \\ &\cdots \end{align*} $$

$F_4 F_n$과 $F_8 F_n$을 보면, $n$이 4의 배수일 때 결과로 나오는 피보나치 항의 인덱스도 모두 4의 배수가 나옴을 알 수 있다. 심지어 그 결과가 의심스러울 정도로 깔끔하고 규칙적이다. 이를 일반화하면 다음과 같이 쓸 수 있다.

$$ F_{4k} F_n = \sum_{i = -k}^{k} {F_{n+4i}} $$

참고로 이 식은 $n$이 작을 때에도 성립하는데, $F_i = F_{i-1} + F_{i-2}$만을 가지고 모든 것을 유도한 것이므로 같은 식으로 $F_i$를 $i<0$으로도 확장하면 된다. 이렇게 확장하면 $\cdots, -8, 5, -3, 2, -1, 1, 0, 1, F_0 = 1, 2, 3, 5, 8, \cdots$ 처럼 되어, $F_{-4-4k} = -F_{4k}$임을 알 수 있다.

잘 정리하면 convolution이 될 것 같이 생기지 않았는가?

$F_{4k}$ 표현의 곱

이제부터는 주어진 두 표현식을 적당히 변형해서 $\sum a_i F_{4i}$ 형태로 만들어놓았다고 가정한다.

문제를 단순화하기 위해 두 표현식의 길이가 4라고 가정하고 둘을 곱해서 전개해보면 다음과 같다.

a0 F0 (b0 F0 + b1 F4 + b2 F8 + b3 F12)
= a0 b0 F0 + a0 b1 F4 + a0 b2 F8 + a0 b3 F12

a1 F4 (b0 F0 + b1 F4 + b2 F8 + b3 F12)
= a1 b0 (F-4 + F0 + F4) + a1 b1 (F0 + F4 + F8)
+ a1 b2 (F4 + F8 + F12) + a1 b3 (F8 + F12 + F16)

a2 F8 (b0 F0 + b1 F4 + b2 F8 + b3 F12)
= a2 b0 (F-8 + F-4 + F0 + F4 + F8) + a2 b1 (F-4 + F0 + F4 + F8 + F12)
+ a2 b2 (F0 + F4 + F8 + F12 + F16) + a2 b3 (F4 + F8 + F12 + F16 + F20)

a3 F12 (b0 F0 + b1 F4 + b2 F8 + b3 F12)
= a3 b0 (F-12 + F-8 + F-4 + F0 + F4 + F8 + F12)
+ a3 b1 (F-8 + F-4 + F0 + F4 + F8 + F12 + F16)
+ a3 b2 (F-4 + F0 + F4 + F8 + F12 + F16 + F20)
+ a3 b3 (F0 + F4 + F8 + F12 + F16 + F20 + F24)

이를 다시 $F_i$에 대한 계수로 묶어주면 다음과 같다.

F-12 : a3 b0
F-8  : a3 (b0 + b1) + a2 b0
F-4  : a3 (b0 + b1 + b2) + a2 (b0 + b1) + a1 b0
F0   : a3 (b0 + b1 + b2 + b3) + a2 (b0 + b1 + b2) + a1 (b0 + b1) + a0 b0
F4   : a3 (b0 + b1 + b2 + b3) + a2 (b0 + b1 + b2 + b3) + a1 (b0 + b1 + b2) + a0 b1
F8   : a3 (b0 + b1 + b2 + b3) + a2 (b0 + b1 + b2 + b3) + a1 (b1 + b2 + b3) + a0 b2
F12  : a3 (b0 + b1 + b2 + b3) + a2 (b1 + b2 + b3) + a1 (b2 + b3) + a0 b3
F16  : a3 (b1 + b2 + b3) + a2 (b2 + b3) + a1 b3
F20  : a3 (b2 + b3) + a2 b3
F24  : a3 b3

뭔가 convolution은 아니면서 convolution으로 해석하고 싶어지는 모양이 드러나기 시작한다. 여기서 한 단계만 더 나아가면 된다. 그 한 단계는 바로 누적합 역연산이다. 누적합 역연산이란, 배열 $X$가 주어질 때 $\operatorname{cumsum}(Y) = X$를 만족하는 배열 $Y$를 찾는 것으로, $X = x_0, x_1, x_2, \cdots$일 때 $Y = x_0, x_1 - x_0, x_2 - x_1, x_3 - x_2, \cdots$가 된다.

위의 각 피보나치 수의 계수에 누적합 역연산을 적용하면 다음과 같다. (규칙을 더 확실하게 보여주기 위해 마지막에 0 하나를 추가한 후 적용하였다. 실제 결과값은 변하지 않는다.)

a3 b0
a3 b1 + a2 b0
a3 b2 + a2 b1 + a1 b0
a3 b3 + a2 b2 + a1 b1 + a0 b0
        a2 b3 + a1 b2 + a0 b1 - a0 b0
                a1 b3 + a0 b2 - a0 b1 - a1 b0
                        a0 b3 - a0 b2 - a1 b1 - a2 b0
                              - a0 b3 - a1 b2 - a2 b1 - a3 b0
                                      - a1 b3 - a2 b2 - a3 b1
                                              - a2 b3 - a3 b2
                                                      - a3 b3

갑자기 2개의 convolution이 너무 명확하게 튀어나왔다. 앞부분은 $\{a_3, a_2, a_1, a_0\} \times \{b_0, b_1, b_2, b_3\}$의 계수를 순서대로 더해주고 있고, 뒷부분은 $\{a_0, a_1, a_2, a_3\} \times \{b_0, b_1, b_2, b_3\}$의 계수를 순서대로 빼주고 있다. 이는 두 표현식의 길이가 같다면 얼마나 길든 상관없이 똑같이 성립한다.

따라서, 두 $F_{4k}$ 표현식의 곱의 $F_{4k}$ 표현식을 구하려면 다음과 같이 하면 된다.

  • $a_i$와 $b_i$의 convolution과, $a_i$의 reverse와 $b_i$의 convolution을 구한다.
  • 위 그림처럼 결과값을 대응시켜 뺀 후 전체의 누적합을 구한다.
  • 음의 인덱스에 해당하는 계수를 같은 절대값을 갖는 양의 인덱스의 계수에서 뺀다.

전처리와 후처리

가장 어려운 부분을 풀었다. 이제 원래 문제를 풀려면 제켄도르프 표현을 $F_{4k}$ 표현으로 바꿔서(전처리) 위 알고리즘을 적용한 후 다시 $F_{4k}$ 표현을 제켄도르프 표현으로 바꾸면 된다(후처리).

전처리는 4의 배수가 아닌 인덱스의 계수를 $F_i = F_{i-1} + F_{i-2}$를 이용하여 아래로 이동시키면 된다. 단, 무지성으로 하면 계수의 크기가 점점 커지기 때문에, 더 높은 $F_{4k}$ 항에 가능한 한 큰 계수를 남기고 이동하도록 처리를 잘 해주어야 한다.

전처리를 잘 했다면 모든 $F_{4k}$의 계수를 10 이하로 만들 수 있다. 이 상태에서의 convolution은 22289. 큰 수 곱셈 (3)의 하위호환이므로, 이 문제를 푸는 FFT 또는 NTT 코드가 있다면 그대로 가져다 쓰면 된다.

후처리는 Fibonacci Sums에서 썼던 알고리즘을 log번 반복하는 것으로 해결할 수 있다.

증명?

증명은… 없다. 이 글에 나오는 모든 과정은 스트레스 테스트를 짜서 반례가 안 나오는 것만 확인했다.