传送门
据斐波那契数列的特性，可知
fibn\text{ }\text{ }\text{ }\text{ }fib_{n} fibn
=fibn−1+fibn−2=fib_{n-1}+fib_{n-2}=fibn−1 +fibn−2
=2fibn−2+fibn−3=2fib_{n-2}+fib_{n-3}=2fibn−2 +fibn−3
=3fibn−3+2fibn−4=3fib_{n-3}+2fib_{n-4}=3fibn−3 +2fibn−4
=5fibn−4+3fibn−5=5fib_{n-4}+3fib_{n-5}=5fibn−4 +3fibn−5
=fibm+1fibn−m+fibmfibn−m−1=fib_{m+1}fib_{n-m}+fib_{m}fib_{n-m-1}=fibm+1 fibn−m +fibm fibn−m−1 .
所以我们可以根据这个解题：
当nnn为奇数时，
fibn=(fib(n−1)/2)2+(fib(n+1)/2)2fib_n=(fib_{(n-1)/2})^2+(fib_{(n+1)/2})^2fibn =(fib(n−1)/2 )2+(fib(n+1)/2 )2.
当nnn为偶数时，
fibn=fibn/2(fibn/2−1+fibn/2+1)fib_n=fib_{n/2}(fib_{n/2-1}+fib_{n/2+1})fibn =fibn/2 (fibn/2−1 +fibn/2+1 ).
所以我们就可以用分治方法解
代码如下
感谢@不是很邪恶的暑假神提供的map解法！
时间复杂度：O(log2n)O(\log^2n)O(log2n).
