# Fibonacci Sequence 快速冪

一般的 **`Fibonacci Sequence`** 可用 `Recursion` 或是 `Iterator` 的方式計算，時間複雜度分別為 **`O(2^N)`**、**`O(N)`**，但是當 **n <= 10^18^** 時，兩種方法皆無法有效率的求出答案。

$$
F_1 = 1
$$

$$
F_2 = 1
$$

$$
F_n = F_{n-1} + F_{n-2}
$$

因此透過上面公式的觀察，我們得出下列的矩陣關係。

$$
1.\left[
\begin{array}{aaa}
F_n \\
F_{n-1} \\
\end{array}
\right] =
\left[
\begin{array}{bbb}
1 & 1 \\
1 & 0 \\
\end{array}
\right]
\left[
\begin{array}{aaa}
F_{n-1} \\
F_{n-2} \\
\end{array}
\right]。
$$
$$
2.\left[
\begin{array}{aaa}
F_n \\
F_{n-1} \\
\end{array}
\right] =
\left[
\begin{array}{bbb}
1 & 1 \\
1 & 0 \\
\end{array}
\right]^n
\left[
\begin{array}{aaa}
1 \\
0 \\
\end{array}
\right]。
$$
$$
3.
\left[
\begin{array}{bbb}
1 & 1 \\
1 & 0 \\
\end{array}
\right]^n =
\left[
\begin{array}{bbb}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1} \\
\end{array}
\right]。
$$

假設

$$
X =
\left[
\begin{array}{bbb}
1 & 1 \\
1 & 0 \\
\end{array}
\right]。
$$

如果直接暴力讓 **`X`** 乘上 `n` 次，時間複雜度同樣為 **`O(N)`**。
但其實還有另一種更有效率的方法，就是利用下圖的數學特性。


> **EXAMPLE :**
> n = 86。
> * X^86^ = ( X^43^ * X^43^ )
> * X^43^ = **X** ( X^21^ * X^21^ )
> * X^21^ = **X** ( X^10^ * X^10^ )
> * X^10^ = ( X^5^ * X^5^ )
> * X^5^ = **X** ( X^2^ * X^2^ )
> * X^2^ = ( X * X )

* 透過遞迴的方式不斷將 `指數項` 縮小。
* 指數項為 `偶數` 時 ---> 回傳值相乘。
* 指數項為 `奇數` 時 ---> 回傳值相乘，並乘上 `X`。

透過這樣的方式， **`X[0][0]`** 就會是答案，且可以大幅減少計算次數，時間複雜度降到 **`O(logN)`**。

### Approach 1 : Recursion
**`O(2^n)`** **`TLE`**

#include<iostream>
#include<vector>
using namespace std;

#define MOD 1000000007

int Fibonacii(int n){
	if(n == 1 || n == 2)	return 1;
	
	return Fibonacii(n-1) + Fibonacii(n-2);
}

int main(void){
	int n;
	
	while(cin >> n){
		cout << Fibonacii(n) << endl;
	}
}

### Approach 2 : Iterator
**`O(N)`** **`TLE`**

#include<iostream>
#include<vector>
using namespace std;

#define MOD 1000000007

int main(void){
	vector<int> F({0, 1, 1});
	int n;
	
	while(cin >> n){
		for(int i = 3; i<=n; i++){
			F[i] = (F[i-1] + F[i-2]) % MOD;
		}
		
		cout << F[n] << endl;
	}
}

### Approach 3 : 快速冪
**`O(logN)`**

#include<iostream>
using namespace std;

#define mod 1000000007

class matrix{
	public :
		friend matrix operator*(const matrix x, const matrix y);
		matrix operator%(int m);
		
		FirstElement(){return array[0][0];}

	private :	
		long long int array[2][2] = {{1,1}, {1,0}};
};


matrix operator*(const matrix x, const matrix y){
	matrix temp;
	
	for(int i=0; i<2; i++){
		for(int j=0 ; j<2; j++){
			temp.array[i][j] = 0;
			for(int k=0; k<2; k++){
				temp.array[i][j] += x.array[i][k] * y.array[k][j] % mod;
			}
		}
	}
	
	return temp;
}

matrix matrix::operator%(int m){
	matrix temp;
	
	for(int i=0; i<2; i++){
		for(int j=0 ; j<2; j++){
			temp.array[i][j] = array[i][j] % mod;
		}
	}
	
	return temp;
}

matrix pow(matrix A, long long int n){
	matrix temp;
	if(n == 1)	return temp;

	temp = pow(A, n/2);
	
	if(n % 2 == 0)	return temp * temp % mod;	// even
	else	return A * temp * temp % mod;		// odd
}


int main(void){
	// input <= 10^18
	
	long long int input;
	matrix A;
	
	while(cin >> input){
		if(input <= 2)	cout << "1" << endl;
		else{
			matrix ans = pow(A, input-1);
			cout << ans.FirstElement() << endl;
		}
	}
	
}