Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment