模板及讲解

通项公式

$$
F(n)=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^n - \left(\frac{1-\sqrt 5}{2}\right)^n\right]
$$

技巧

1、斐波那契数列增长快
2、与斐波那契数列相关的大数据递推，可以用矩阵优化

恒等式

(前缀和) 1、$f(1)+f(2)+f(3)+ \dots +f(n)=f(n+2)-1$
(平方前缀和) 2、$f(1)^2+f(2)^2+f(3)^2+ \dots +f(n)^2=f(n)f(n+1)$
(奇数项) 3、$f(1)+f(3)+f(5)+ \dots +f(2n-1)=f(2n)$
(偶数项) 4、$f(2)+f(4)+f(6)+ \dots +f(2n)=f(2n+1)-1$
5、$f(m)f(n-m+1)+f(m-1)f(n-m)=f(n), n \leq m$
6、$f(n-1)f(n+1)=f(n)^2+(-1)^n$

性质

1、$\gcd(f(n), f(m))=f(\gcd(n, m))$
2、$n | m \Leftrightarrow f(n) | f(m)$
3、类斐波那契数列 $h(n)=a \times f(n-2) + b \times f(n-1)，a=h(1), b=h(2)$

例题

P1306 斐波那契公约数

运用$\gcd(f(n), f(m))=f(\gcd(n, m))$缩小范围再矩阵快速幂优化。