matrix

I’ve been read Jane Eyre recently; I really love it.

矩阵快速幂

矩阵乘法满足结合律和分配律，不满足交换律

快速幂运算

如果数据太大，记得开 long long

int power (int a, int n) { // a^n
    int ans;
    if (n == 0) ans = 1;
    else {
        ans = power(a * a, n / 2);
        if (n % 2 == 1) ans *= a;
    }
    return ans;
}

int power(int a, int n) {
    int ans = 1;
    while(n) {
        if (n % 2) ans = ans * a;
        a = a * a;
        n = n / 2'
    }
    return ans;
}

矩阵快速幂

应用：有以下递推式

$$f[n]=f[n-1]+f[n-2]$$

构造矩阵

$$\begin{bmatrix} f[n]\\ f[n - 1] \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix} \begin{bmatrix} f[n-1]\\ f[n - 2] \end{bmatrix}$$

转换

$$C(n) = \begin{bmatrix} f[n]\\ f[n - 1] \end{bmatrix} \\ B = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}$$

得到新的递推式：