一些废话

定义斐波那契数列为：

$$
\begin{equation}
\begin{cases}
Fib(1)=1 \\
Fib(2)=1 \\
Fib(i)=Fib(i-1)+Fib(i-2)
\end{cases}
\end{equation}
$$

$\log _ 2 N$复杂度内求 Fib(N) 可以用矩阵乘法做

但是我就是不喜欢咋啦？╭(╯^╰)╮

我问 Pyh 神犇他的递归求的方法，他很耐心地跟我讲解了，在此感谢～

这个方法使用的是递归求，不需要矩阵乘法快速幂啥的。。。编程复杂度比较低吧。。。

公式的证明

这里证明一个公式：

$$Fib(n)=Fib(m)\times Fib(n-m+1)+Fib(m-1)\times Fib(n-m)$$

证明：

$Fib(n)$
$=Fib(n-1)+Fib(n-2)$
$=2\times Fib(n-2)+Fib(n-3)$
$=3\times Fib(n-3)+2\times Fib(n-4)$
$=Fib(4)\times Fib(n-3)+Fib(3)\times Fib(n-4)$

以此类推

可以得到：

$$Fib(n)=Fib(m)\times Fib(n-m+1)+Fib(m-1)\times Fib(n-m)$$

方法解释

根据上面得到的公式，我们可以得到：

$$Fib(2n)=Fib(n)\times Fib(n+1)+Fib(n-1)\times Fib(n)$$

怎么得到的呢？就是设公式中的 m 为 n，即 2n 的 1/2
然后再拆开移项：

$Fib(2n)$
$=Fib(n)\times [Fib(n)+Fib(n-1)]+Fib(n-1)\times Fib(n)$
$=Fib^2(n)+2Fib(n)Fib(n-1)$

然后依然是 m 为 n，我们求 Fib(2n-1)

$Fib(2n-1)$
$=Fib^2(n)+Fib^2(n-1)$

（可以直接带入原公式得到）

那么正片来了：

我们搞个递归函数 dfs(a)

当 $a = 1$时，$Fib(a)=1,Fib(a-1)=0$

当 $a = 2$时，$Fib(a)=Fib(a-1)=1$

当 $a$为偶数，我们可以 dfs(a/2)，求出 $Fib(\frac a 2),Fib(\frac a 2-1)$

然后 $Fib(a)$就等于 $Fib^2(\frac a 2)+2Fib(\frac a 2)Fib(\frac a 2-1)$

$Fib(a-1)$就等于 $Fib^2(a/2)+Fib^2(a/2-1)$

当 a 为奇数时，我们可以 dfs(a-1)，求出 $Fib(a-1),Fib(a-2)$，然后加起来得到 $Fib(a)$

这样一直递归下去就能最后求得 $Fib(n)$了

复杂度 $O(\log_2n)$

代码：

LL cur, pre;

void dfs(LL a)
{
    if (a == 1){ pre = 0, cur = 1; return; }
    if (a == 2){ pre = cur = 1; return; }
    if (a & 1) { dfs(a - 1), swap(pre, cur), cur = (pre + cur) % m; return; }
    dfs(a >> 1);
    LL tem = cur;
    cur = (cur * cur % m + ((cur * pre % m) << 1) % m) % m;
    pre = (tem * tem % m + pre * pre % m) % m;
}