# (矩陣)快速冪

快速冪
---

* 把次方拆成一半，如果是奇數的話先拿掉一個次方
* ex: $2^{18}$可以拆成兩個$2^9$，因為$2^9$是奇數所以拆成$2^8\times2^1$，再把$2^8$拆為兩個$2^4$。以此類推到$2^1$。
* 複雜度$O(log(n))$

程式碼：

遞迴：

long long fastpow(long long a, long long b) {
    if (b == 0) return 1;
    long long res = fastpow(a, b / 2);
    if (b % 2)
    return res * res * a;
    else
    return res * res;
}

iteration:

long long fastpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

矩陣快速冪
---

* 證明：https://math.stackexchange.com/questions/784710/how-to-prove-fibonacci-sequence-with-matrices/784723#784723

$A^{n+1}=\begin{pmatrix}F_{n+2} & F_{n+1} \\ F_{n+1} & F_{n}
\end{pmatrix}$

* $fib(n)=A^{n-1}[0][0]$
* 用快速冪方法

matrix:

struct mat{
    long long a[2][2]={0};

    mat operator * (mat &inp){
        mat res;
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j)
                for(int k=0;k<2;++k)
                    res.a[i][j]+=a[i][k]*inp.a[k][j];
        return res;
    }
};

快速冪：

mat base;

mat fpow(long long b){
    if(b==1) return base;
    mat res=fpow(b/2);
    if(b & 1)
        return res*res*base;
    else
        return res*res;
}

主程式：

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    base.a[0][0]=1;
    base.a[0][1]=1;
    base.a[1][0]=1;
    long long n;
    
    cin>>n;
    if(n==0) cout << 0 << NL;
    else if(n==1) cout << 1 << NL;
    else cout << fpow(n-1).a[0][0] << NL;
}

大小矩陣通用模板：

struct mat{
    vector<vector<LL>> a;
    int wdt, len;
    // initilize size of matrix
    mat(int x, int y){
        a.resize(x, vector<LL>(y,0));
        len=x;
        wdt=y;
    }

    mat operator*(mat &inp){
        mat res(len, inp.wdt);
        for(int i=0;i<len;++i)
            for(int j=0;j<inp.wdt;++j)
                for(int k=0;k<wdt;++k)
                    res.a[i][j]+=a[i][k]*inp.a[k][j];
        return res;
}
};