/*
思路一:斐波那契数列, 等价于leetcode70 爬楼梯leetcode-cn.com/problems/climbing-stairs/
fib[0]=0, fib[1]=1
f[i]=f[i-1] + f[i-2]
由于斐波那契数列是差分方程，所以可以使用矩阵快速幂、通项公式
方法一:动态规划
方法二:矩阵快速幂
矩阵 + 快速幂，时间复杂度O(logn)
[fi[1], fi[0]] = [1, 0]
[f[n], f[n-1]] = [[1, 1], [1, 0]]^(n-1) * [f[1], f[0]]
求matrix = [[1, 1], [1, 0]]^(n-1)
因为f[1]=1, f[0]=0; 所以f[n] = matrix[0][0]
难点：
快速幂计算矩阵时，初始值是单位矩阵。
计算矩阵元素时，需要同时并行计算

方法三:二阶常系数齐次差分方程的通项公式
y[2] - y[1] - y[0]=0
通项公式：r^2 - r - 1=0
r=(-b±√(b^2+4ac)) / 2a, r1 = (1+√5)/2, r2 = (1-√5)/2
通解y* = c1*r1^x + c2*r2^x
带入y[0]=0, y[1]=1，求得c1=1/√5, c2=-1/√5
*/
/*方法1*/
class Solution {
public:
    int Fibonacci(int n) {
        if (n==0) return 0;
        int a = 0, b = 1, c = 1;
        for (int i = 0; i < n-1; i ++) {
            c = a + b; // n=1, c=fib[2]
            a = b;
            b = c;
        }
        return b;
    }
};
/*方法2*/
class Solution {
public:
    int Fibonacci(int n) {
        using ull = unsigned long long;
        if (n==0) return 0;
        vector<ull> a = {1,1,1,0}; // 2d-matrix [[1, 1], [1, 0]]
        int p = n-1;
        vector<ull> t = a, res = {1,0,0,1}; //res初始化是单位矩阵
        while (p) {
            if (p & 1)
                //注意并行计算
                tie(res[0], res[1], res[2], res[3]) = make_tuple(
                    res[0]*t[0] + res[1]*t[2],
                    res[0]*t[1] + res[1]*t[3],
                    res[2]*t[0] + res[3]*t[2],
                    res[2]*t[1] + res[3]*t[3]
                );
            tie(t[0], t[1], t[2], t[3]) = make_tuple(
                t[0]*t[0] + t[1]*t[2],
                t[0]*t[1] + t[1]*t[3],
                t[2]*t[0] + t[3]*t[2],
                t[2]*t[1] + t[3]*t[3]
            );
            p >>= 1;
        }
        return int(res[0]);
    }
};
/*方法3*/
class Solution {
public:
    int Fibonacci(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1 + sqrt5) / 2, n) - pow((1 - sqrt5) / 2, n);
        return (int)round(fibn / sqrt5);
    }
};