矩阵快速幂求Fib前n项和

简单构造如下等式

$$ \begin{pmatrix} f\small(n + 1) & f\small(n) & s\small(n) \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1\\\ 1 & 0 & 0\\\ 0 & 0 & 1 \end{pmatrix} = \begin{pmatrix} f\small(n + 2) & f\small(n + 1) & s\small(n + 1) \end{pmatrix} $$

则我们可以令$A = \begin{pmatrix} 1 & 1 & 1\\\ 1 & 0 & 0\\\ 0 & 0 & 1 \end{pmatrix}$

于是有

$$ \begin{pmatrix} f\small(n + 1) & f\small(n) & s\small(n) \end{pmatrix} \cdot A = \begin{pmatrix} f\small(n + 2) & f\small(n + 1) & s\small(n + 1) \end{pmatrix} $$

根据递推式，我们可以轻松得到通项

$$ \begin{pmatrix} f\small(1) & f\small(0) & s\small(0) \end{pmatrix} \cdot \begin{pmatrix} 1 & 1 & 1\\\ 1 & 0 & 0\\\ 0 & 0 & 1 \end{pmatrix}^n = \begin{pmatrix} f\small(n + 1) & f\small(n) & s\small(n) \end{pmatrix} $$

即

$$ \begin{pmatrix} f\small(1) & f\small(0) & s\small(0) \end{pmatrix} \cdot A ^ n = \begin{pmatrix} f\small(n + 1) & f\small(n) & s\small(n) \end{pmatrix} $$

接下来可以直接用矩阵快速幂求出 $A^n$ 便可以在 $O(\log n)$ 的时间复杂度下计算出答案

Code

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;

void qmul(int a[][3], int b[][3], int c[][3]) {
    static int t[3][3];
    memset(t, 0, sizeof t);
    for (int i = 0; i < 3; ++ i) {
        for (int j = 0; j < 3; ++ j) {
            for (int k = 0; k < 3; ++ k) {
                t[i][j] = (t[i][j] + (LL)a[i][k] * b[k][j] % m) % m;
            }
        }
    }
    memcpy(c, t, sizeof t);
}
int main() {
    int a[N][N] = {1, 0, 0};
    int b[N][N] = {
        {1, 1, 1},
        {1, 0, 0},
        {0, 0, 1}
    };
    cin >> n >> m;
    for (int i = n; i; i >>= 1) {
        if (i & 1) qmul(a, b, a);
        qmul(b, b, b);
    }
    cout << a[0][2] << endl;
    return 0;
}