莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

$设\ F_n=\begin{bmatrix}f_n&f_{n+1}&S_n\end{bmatrix}$

$\begin{aligned}F_n\cdot A & = F_{n+1} \\\\ \begin{bmatrix}f_n&f_{n+1}&S_n\end{bmatrix}\begin{bmatrix}a_{11}&a_{12}&a_{13}\\\\a_{21}&a_{22}&a_{23}\\\\a_{31}&a_{32}&a_{33}\end{bmatrix}& = \begin{bmatrix}f_{n+1}&f_{n+2}&S_{n+1}\end{bmatrix}\\\\\begin{bmatrix}a_{11}&a_{12}&a_{13}\\\\a_{21}&a_{22}&a_{23}\\\\a_{31}&a_{32}&a_{33}\end{bmatrix}&=\begin{bmatrix}0&1&0\\\\1&1&1\\\\0&0&1\end{bmatrix}\end{aligned}$

$则\ F_n=F_1\cdot A^{n-1}$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

int n,m;

// 1 * 3 矩阵与 3 * 3 矩阵相乘
void mul(int c[],int a[],int b[][3])
{
    int temp[3]={0};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
    memcpy(c,temp,sizeof temp);
}

// 3 * 3 矩阵与 3 * 3 矩阵相乘
void mul(int c[][3],int a[][3],int b[][3])
{
    int temp[3][3]={0};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;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 f[3]={1,1,1};
    int a[3][3]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };

    n--;
    while(n) //矩阵快速幂
    {
        if(n&1) mul(f,f,a);
        mul(a,a,a);
        n>>=1;
    }

    cout<<f[2]<<endl;

    return 0;
}