题解 | #Fibonacci 第 n 项#

思路：

由于数据范围过大，所以递推已经无法满足要求，尝试将递推式的运算转换为矩阵的运算

用 $f_{i}f\_i$ 来表示斐波那契数列的第 $ii$ 项

递推式：$f_i=1\times f_{i-1}+1\times f_{i-2}f\_i\; =\; 1\backslash times\; f\_\{i-1\}\; +\; 1\; \backslash times\; f\_\{i-2\}$

矩阵运算：

进而推广到全部 ，$FF$ 采用一个一维数组来表示即可，$f_{n}f\_n$ 和 $f_{n+1}f\_\{n+1\}$ 即为 $F[0]F[0]$ 和 $F[1]F[1]$，使用矩阵快速幂即可快速求解，最终答案即为 $F[0]F[0]$

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 2;

int n, m;
int f[N] = {1, 1};//初始矩阵 f1 = f2 = 1;
int a[N][N] = {
    {0, 1},
    {1, 1}
};

//计算矩阵a乘b，答案保存在a当中
void mul(int a[], int b[][N])
{
    int tmp[N] = {0};
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            tmp[i] = (tmp[i] + (LL)a[j] * b[j][i]) % m;
    memcpy(a, tmp, sizeof tmp);
}

//计算矩阵a乘b，答案保存在a当中
void mul(int a[][N], int b[][N])
{
    int tmp[N][N] = {0};
    for (int i = 0; i < N; i ++)
        for (int j = 0; j < N; j ++)
            for (int k = 0; k < N; k ++)
                tmp[i][j] = (tmp[i][j] + (LL)a[i][k] * b[k][j]) % m;
    memcpy(a, tmp, sizeof tmp);
}

int main()
{
    cin >> n >> m;

    n --;
    while (n)
    {
        if (n & 1) mul(f, a);  // 类比快速幂 res = res * a
        mul(a, a);  // a = a * a
        n >>= 1;
    }

    cout << f[0] << endl;

    return 0;
}