2855 Fibonacci Check-up 矩阵的应用

两个数论公式： f(k) = ( (1+sqrt(5)) / 2 ) ^ k - ( (1-sqrt(5)) / 2) ^ k (1+a)^n = Sum(C(k|n) (a^k)) 推导过程： Sum(C(k|n) f(k)) = Sum(C(k|n) ( (1+sqrt(5)) / 2 ) ^ k - ( (1-sqrt(5)) / 2) ^ k) = Sum(C(k|n) (1+sqrt(5)) / 2 ) ^ k) - Sum(C(k|n) * (1-sqrt(5)) / 2 ) ^ k) = ( (3+sqrt(5)) / 2 ) ^ k - ( (3-sqrt(5)) / 2) ^ k = ( (1+sqrt(5)) / 2 ) ^ 2k - ( (1-sqrt(5)) / 2) ^ 2k = f(2k) 构造矩阵是浮云 Fn(1,2) = |f(n) f(n-1)| F1(1,2) = |f(1) f(1)| = |1 0| A(2,2) = |1 1| |1 0|