分析

以下两个问题都使用矩阵乘法的方式解决，因为矩阵大小分别为$2 \times 2$或者$3 \times 3$的，两矩阵乘法计算次数可以忽略不计，则时间复杂度为$O(log(n))$的。

求斐波那契数列

• 设$F_n = [f_n, f_{n+1}]$，则有如下递推公式：

$$ [f_n, f_{n+1}] \left[ \begin{matrix} 0 & 1 \\\\ 1 & 1 \end{matrix} \right] = [f_{n+1}, f_{n+2}] $$

• 因此，有如下递推公式：

$$ F_n = F_1 \left[ \begin{matrix} 0 & 1 \\\\ 1 & 1 \end{matrix} \right] ^ {n - 1} \quad \quad F_1 = [1, 1] $$

• 假如设A表示那个变换矩阵，则我们对$A^{n-1}$进行快速幂求解即可。

求斐波那契数列前n项和

• 设$F_n = [f_n, f_{n+1}, S_n]$，其中$S_n$表示数列前n项和，则有如下递推公式：

$$ [f_n, f_{n+1}, S_n] \left[ \begin{matrix} 0 & 1 & 0 \\\\ 1 & 1 & 1 \\\\ 0 & 0 & 1 \end{matrix} \right] = [f_{n+1}, f_{n+2}, S_{n+1}] $$

• 因此，有如下递推公式：

$$ F_n = F_1 \left[ \begin{matrix} 0 & 1 & 0 \\\\ 1 & 1 & 1 \\\\ 0 & 0 & 1 \end{matrix} \right] ^ {n - 1} \quad \quad F_1 = [1, 1, 1] $$

• 假如设A表示那个变换矩阵，则我们对$A^{n-1}$进行快速幂求解即可。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 3;

int n, m;  // 求前n项和对m取模

// c[] = a[] * b[][]
void mul(int c[], int a[], int b[][N]) {

    int temp[N] = {0};
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            temp[i] = (temp[i] + (LL)a[j] * b[j][i]) % m;
    memcpy(c, temp, sizeof temp);
}

// c[][] = a[][] * b[][]
void mul(int c[][N], int a[][N], int b[][N]) {

    int temp[N][N] = {0};
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            for (int k = 0; k < N; k++)
                temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(c, temp, sizeof temp);
}

int main() {

    cin >> n >> m;

    int f1[3] = {1, 1, 1};
    int a[N][N] = {
        {0, 1, 0},
        {1, 1, 1},
        {0, 0, 1}
    };

    n--;
    while (n) {
        if (n & 1) mul(f1, f1, a);  // f1 = f1 * a
        mul(a, a, a);  // a = a * a
        n >>= 1;
    }

    cout << f1[2] << endl;

    return 0;
}