백준 8506번: Leonardo's Numbers

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

8506번: Leonardo's Numbers

---

이 문제를 풀 때 크게 두 가지 방향으로 접근할 텐데,

 

• Berlekamp - Massey 같은 방법론으로 점화식을 얻어낸 뒤, Kitamasa나 FFT 같은 걸로 값을 구하기
• 그냥 진짜 깡 일반항을 구해버리기

후자가 매우 힘들어 보이지만, 전자에도 함정이 있음을 고려하면, 또 사전지식의 양까지 생각해보면 아주 큰 차이는 없는 듯 하기도 합니다.

 

일단 저는 후자로 풀었는데, 이 방법으로 간 이유는 인터넷에 결과가 이미 나와있기 때문이었습니다.

---

문제에서 주어진 Leonardo's Numbers에 대해 다음이 성립합니다.

$$ L_{n} = 2 \times f_{n+1} - 1 $$

유도는 $L_{n}$의 점화식의 양변에 1을 더하면 감을 잡을 수 있습니다.

 

이제 답을 구하는 것은 피보나치 수의 $k$제곱의 합을 구하는 문제로 환원됐습니다.

$$ \sum_{i=0}^{n} L_{i}^{k} = \sum_{i=0}^{n} \left ( 2f_{i+1} - 1 \right )^{k} = \sum_{i=0}^{k} \binom{k}{i} 2^{i} (-1)^{k-i} \left ( \sum_{j=1}^{n+1} f_{j}^{i} \right ) $$

$k$의 범위가 충분히 작아서, binomial coefficient는 $O(k^{2})$에 구해줍니다. 이제 모듈러 연산만 신경쓰면 됩니다.

 

링크에서 제시된 공식 중 하나를 보겠습니다.

$$ \sum_{i=0}^{n} f_{i}^{4} = \frac{f_{4n+2} - 4(-1)^{n}f_{2n+1} + 6n + 3}{25} $$

왜 모듈러 연산에 신경을 써야 하냐면, 분자를 계산할 때 나이브하게 $10^{9}$를 mod로 놓고 풀면 틀리기 때문입니다.

 

이런 경우, 어차피 결괏값이 정수임이 보장되어 있다면 분모의 모듈러 곱셈 역원을 구해서 푸는 경우가 많습니다.

 

그러나, 모듈러 곱셈 역원을 구하려면 분모와 modulo가 서로소여야 하므로 역원을 구하는 풀이가 불가능합니다.

 

이를 효과적으로 우회하는 방법은 분모가 $d$일 때 분자의 $\textrm{mod} \;\; (d \times 10^{9})$ 값을 구하는 것입니다.

 

여기서 생길 수 있는 의문은, modulo가 그렇게 커져도 올바르게 답을 구할 수 있느냐입니다.

 

__int128 type을 쓸 경우 $10^{19}$까지는 modulo가 커져도 무리가 없습니다. 그보다 커지면 덧셈, 곱셈을 따로 함수를 구현해서 써야 합니다.

 

이 문제에서는, modulo가 아무리 커져도 $10^{21}$ 수준입니다. 따라서 곱셈 함수만 구현해서 쓰면 충분합니다.

 

전체 코드가 너무 길기 때문에, 우선 $\sum_{i=1}^{n} f_{i}^{k}$ 부분의 코드를 보여드리겠습니다.

else if (K == 7) {
        /*
         * sum_{i=0}^{n} f_{i}^{7} = (88f_{7n+4} + 22f_{7n+2}
                                      - 812(-1)^nf_{5n+3} - 406(-1)^nf_{5n+1}
                                      + 6699f_{3n+2}
                                      - 22330(-1)^nf_{n-1}
                                      + 17375)/79750
        */
        u128 tempmod = mod * 79750;
       
        u128 temp = 0;
        temp = (temp + 88 * Fibonacci_modular(N*7 + 4, tempmod)) % tempmod;
        temp = (temp + 22 * Fibonacci_modular(N*7 + 2, tempmod)) % tempmod;
       
        temp = (temp + (N % 2 ? 812 : tempmod-812) * Fibonacci_modular(N*5 + 3, tempmod)) % tempmod;
        temp = (temp + (N % 2 ? 406 : tempmod-406) * Fibonacci_modular(N*5 + 1, tempmod)) % tempmod;
       
        temp = (temp + 6699 * Fibonacci_modular(N*3 + 2, tempmod)) % tempmod;
       
        temp = (temp + (N % 2 ? 22330 : tempmod-22330) * Fibonacci_modular(N - 1, tempmod)) % tempmod;
       
        temp = (temp + 17375) % tempmod;
       
        answer = (temp / 79750) % mod;
    }

이런 코드를 $0 \leq k \leq 13$에 대해 작성해주면 모든 경우의 수를 커버할 수 있습니다.

 

그리고, $f_{n}$ 자체는 다음 식으로부터 구합니다. Binary Exponentiation을 통해 $O(\log n)$에 구할 수 있습니다.

$$ \begin{bmatrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n} $$

이제 $\sum_{i=0}^{n} L_{i}^{k}$를 구할 수 있습니다. 저는 최대 12ms까지 커팅했습니다.

(C11, 12ms, 1148KB, 제출번호 65993355)

---

코드 테스트를 위해 썼던 데이터들을 보여드리겠습니다.

n	k	$\sum_{i=1}^{n} f_{i}^{k} \;\; \textrm{mod} \;\; 10^{9}$
100	1	078,999,175
10	2	000,004,895
20	3	273,951,280
30	4	855,031,844
20	5	749,231,000
15	6	044,808,010
10	7	824,599,171
	8	387,560,263
	9	597,487,843
	10	696,237,975
	11	490,644,931
	12	654,153,703
	13	410,751,523

주의할 점은, 홀짝성에 기반한 코드가 들어가므로 홀수일 때, 짝수일 때를 골고루 테스트해줘야 올바른 테스트가 된다는 것입니다.

 

추가로 $k=0$일 때는 $0^{0}$ 이슈가 발생하지 않게 함수의 정의를 명확히 하고 구현해야 합니다.

 

다음은 실제 문제에 적용할 수 있는 테스트 데이터입니다.

n	k	$\sum_{i=0}^{n} L_{i}^{k} \;\; \textrm{mod} \;\; 10^{9}$
5	3	000,004,258
20	11	505,930,691
30	13	620,140,483

출처가 ONTAK이었는데 공식 데이터셋을 구하기 힘들어서 그냥 울프람알파에서 열심히 계산했습니다.

---

Kitamasa 같은 걸 안 쓰면 시간을 더 줄이기는 힘든 것 같습니다. 그러려면 Berlekamp Massey도 공부해야 하는데, 언젠가 한 번 제대로 공부하고 싶은 알고리즘입니다...