令 $a=\dfrac{1+\sqrt5}{2},b=\dfrac{1-\sqrt5}{2}$。

我们有结论：对于 $n\ge 2$，$F_{n+1}=F_{n-1}+F_{n}$。

证明：

注意到：

$$\begin{aligned}F_n=F_n(a+b)&=\dfrac{a^{n+1}-b^{n+1}+a^nb-ab^n}{\sqrt 5}\\&=F_{n+1}+abF_{n-1}\\&=F_{n+1}-F_{n-1}\end{aligned} $$

因此 $F_{n+1}=F_{n-1}+F_n$。

$\mathcal{Q.E.D.}$

前 $\mathcal{O}(1)$ 项的值容易求出，然后使用 http://192.168.121.12/p/P387/solution/67caa97a11ce04ce230e63f5 中提到的做法即可 $\mathcal{O}(\log n)$。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	double m=(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n))/sqrt(5);
	printf("%.2lf",m);
	return 0;
}

l = [1,1]
n = int(input())
if n > 0:
    for i in range(n-2):
        l.append(l[-1]+l[-2])
    print('%.2f'%l[-1])
else:
    print('0.00')

由题意可知要求斐波那契数列的第n项。

代码中的l为斐波那契数列。

由于n是自然数，所以需要判断n为0的情况。