fibonacci.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;



//como estamos lidando com número muito grandes, 
//quase sempre trabalharemos com residuos modulares.
const ll MOD = 1e9 + 7;

struct matrix{
	//aqui temos as dimensões da matriz
	int n, m;
	ll v[5][5];

	//inicializamos a matriz com zeros em todas as posições,
	//passando suas dimensões

	matrix(int _n = 0, int _m = 0){
		n = _n, m = _m;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= m; j++) v[i][j] = 0;
		
	}
	
	//aqui temos o algoritmo manual codificado de multiplicação de matrizes

	matrix operator * (matrix ma){
		matrix ans = matrix(n, ma.m);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= ma.m; j++){
				for(int k = 1; k <= m; k++){
					ans.v[i][j] += v[i][k] * ma.v[k][j];
					ans.v[i][j] %= MOD;
				}

			}
		}
		return ans;

	}

	//aqui temos o algoritmo que retorna o resultado da exponenciação rápida.
	//inicializamos a matriz resposta como a matriz identidade

	matrix operator ^(ll k){
		matrix ans = matrix(n, n);
		for(int i = 1; i <= n; i++) ans.v[i][i] = 1;
		bool ok = 0;
		for(ll i = 50; i >= 0; i--){
			if(ok) ans = ans*ans;
			if(k&(1LL<<i)){
				ans = ans*(*this);
				ok = 1;
			}
		}

		return ans;
	}

	//Para fins de debug e correção de erros,
	//essa função imprime a matriz quando necessário.

	void print(){
		printf("n: %d m: %d\n", n, m);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				printf("%lld ",v[i][j] );
			}
			printf("\n");
		}
	}

};




matrix M, base;
int main(){
	ll n;
	scanf("%lld", &n);

	//inicializamos a matriz M
	M = matrix(2, 2);
	M.v[1][1] = 0, M.v[1][2] = 1;
	M.v[2][1] = 1, M.v[2][2] = 1;
	
	//lembre-se,o vetor base nada mais é do que uma matriz de uma linha
	base = matrix(1, 2); 
	base.v[1][1] = 1, base.v[1][2] = 1;

	matrix ans = base * (M^(n-1 ));
	printf("%lld\n", ans.v[1][2]);

}