백준 온라인 저지 - 13716. 피보나치 수열처럼 보이지만...

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

13716번: 피보나치 수열처럼 보이지만...

 

피보나치 수열이 주어질 때,

$$F_1 = 1,\quad F_2 = 2,\quad F_{n+2} = F_n + F_{n+1}$$

아래 수식의 값을 $10^9+7$로 나눈 나머지를 구하는 문제이다.

$$ S(n, k) := \sum_{i=1}^n F_i \cdot i^k $$

 

 

(풀이)

$k$에 대한 점화식을 세워본다. (단, $[P]$의 값은 명제 $P$가 참이면 $1$, 아니면 $0$으로 정의한다.)

$$ S(n, 0) = \sum_{i=1}^n F_i = F_{n+2} - 2 = F_{n} + F_{n+1} - 2 \tag{by induction} $$

$$ \begin{align*} S(n, k) &= \sum_{i=1}^n F_i \cdot i^k = \sum_{i=1}^n (F_{i+1} - F_{i-1}) \cdot i^k \\ &= (\sum_{i=2}^{n+1} F_i \cdot (i-1)^k) - (\sum_{i=0}^{n-1} F_i \cdot (i+1)^k) \\ &= F_n \cdot (n-1)^k + F_{n+1} \cdot n^k - F_0 \cdot 1^k - F_1 \cdot 2^k - \sum_{i=2}^{n-1} F_i \cdot ((i+1)^k - (i-1)^k) \\ &= F_n \cdot (n-1)^k + F_{n+1} \cdot n^k - F_0 \cdot 1^k - F_1 \cdot 2^k \\ &\quad+ F_1 \cdot (2^k - 0^k) + F_n \cdot ((n+1)^k - (n-1)^k) - \sum_{i=1}^{n} F_i \cdot ((i+1)^k - (i-1)^k) \\ &= F_{n+1} \cdot n^k + F_{n} \cdot (n+1)^k - 1 \\&\quad -\sum_{j=0}^k \sum_{i=1}^{n} F_i \cdot \binom{k}{j} \cdot i^j \cdot \left[(+1)^{k-j} - (-1)^{k-j}\right] \\ &= F_{n+1} \cdot n^k + F_{n} \cdot (n+1)^k - 1 - 2 \sum_{j=0}^k \left[(k-j) \:\operatorname{mod}\: 2 = 1\right] \cdot \binom{k}{j} \cdot S(n, j) \end{align*} $$

 

즉, 전체 함수에서 계산되는 피보나치 값은 $F_n$와 $F_{n+1}$ 밖에 없다. 빠른 피보나치 계산 코드만으로도 충분히 맞을 수 있다.