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 3×3 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; | |
| } |
