歪解

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

#include <iostream>
#include <cstdio>
#include <map>
#define int long long
using namespace std;
map <int, int> a;
const int mod = 1e9 + 7;
int fib(long long n){
	if(a[n]) return a[n];
	if(n & 2 == 1){
		int l = fib(n / 2), r = fib((n / 2) + 1);
		return a[n] = (l * l + r * r) % mod;
	}
	else return a[n] = fib(n / 2) * (fib((n / 2) - 1) + fib((n / 2) + 1)) % mod;
}
signed main(){
    a[2] = a[1] = 1;
	long long n;
	cin >> n;
	cout << fib(n);

	return 0;
}

时间复杂度：$O(\log^2n)$.