Solução

Para esse problema vamos primeiro achar uma recursão que represente o problema:

• $f_x = f_{x-1} + f_{x-2} + 1$
• $f_1 = 1$
• $f_0 = 1$

Pois para cada valor de fibonacci, temos que a quantidade de chamadas recursivas é igual a quantidade de $x-1$ mais $x-2$ mais o dele mesmo $1$.

Agora já poderíamos montar uma matriz 3x3 e resolver o problema com exponenciação rápida, porém podemos deixar o problema mais simples por meio de matemática.

Vamos partir da hipótese que $f_x = 2\cdot fib_x -1$:

Podemos verificar para os casos bases que isso é verdade:

• $f_0 = 2\cdot fib_0 - 1 \Rightarrow f_0 = 2\cdot 1 - 1 = 1$
• $f_1 = 2\cdot fib_1 - 1 \Rightarrow f_1 = 2\cdot 1 - 1 = 1$

Para o caso geral temos que:

$f_x = f_{x-1} + f_{x-2} + 1 \\ \Rightarrow f_x = (2\cdot fib_{x-1}-1) + (2\cdot fib_{x-2}-1) + 1\\ \Rightarrow f_x = 2 \cdot (fib_{x-1}+fib_{x-2}) - 1\\ \Rightarrow f_x = 2\cdot fib_x - 1$

Provando assim por indução que $f_x = 2\cdot fib_x - 1$.

Para calcular $fib_x$ podemos usar o fato que dado uma matriz $M = \left[{\begin{array}{cc} 1 & 1 \\ 1 & 0 \\ \end{array} } \right]$, considerando $A = M^n$ sendo $n$ o $n$-ésimo número de Fibonacci, temos que $fib_n = A_{1,1} = (M^n)_{1,1}$.

Com isso podemos calcular $M^n$ usando a representação em binário de $n$, pois $M^n = M^{c_1 + c_2 + \ ...\ c_k} = M^{c_1}\cdot M^{c_2} \ ... \ M^{c_k}$ sendo $c_1$ as potências de dois que compôem $n$, com isso usando essa técnica podemos aplicar a mesma idéia em matrizes, e é claro computando sempre os elementos módulo $b$.

Código:

	#include <bits/stdc++.h>
	using namespace std;
	typedef unsigned long long ull;
	struct mat
	{
	ull m[2][2];
	mat operator* (const mat &rhs) const
	{
	mat ans = {0, 0, 0, 0};
	for (int i = 0; i < 2; i++) {
	for (int j = 0; j < 2; j++) {
	for (int k = 0; k < 2; k++) {
	ans.m[i][j] += m[i][k]*rhs.m[k][j];
	}
	}
	}
	return ans;
	}
	mat operator% (ull x) const
	{
	mat ans = {0, 0, 0, 0};
	for (int i = 0; i < 2; i++) {
	for (int j = 0; j < 2; j++) {
	ans.m[i][j] = m[i][j]%x;
	}
	}
	return ans;
	}
	};
	mat power(mat x, ull b, ull mod)
	{
	mat ans = {1, 0, 0, 1};
	while (b) {
	if (b&1ull) ans = (ans*x) % mod;
	x = (x*x) % mod;
	b >>= 1;
	}
	return ans;
	}
	int main()
	{
	ull n, b;
	cin >> n >> b;
	mat fib = {1, 1, 1, 0};
	fib = power(fib, n, b);
	ull ans = 2ull*fib.m[0][0] - 1;
	ans %= b;
	cout << ans << "\n";
	return 0;
	}

view raw

fib.cpp

hosted with by GitHub