分析

本题有关线性代数的矩阵乘法。
令
$$\begin{array}{ll} &F_{n}= &\begin{bmatrix} f_{n}(第n项) & f_{n+1}(第n+1项) & S_{n}(前n项和)\\ \end{bmatrix} \end{array}$$
$$\begin{array}{ll} &F_{n+1}= &\begin{bmatrix} f_{n+1} & f_{n+2} & S_{n+1}\\ \end{bmatrix} \end{array}$$
由这两个矩阵可以计算出所要进行运算的矩阵A:

$$\begin{array}{ll} &A= &\begin{bmatrix} [0 & 1& 0]\\ [1 & 1& 1]\\ [0 & 0& 1]\\ \end{bmatrix} \end{array}$$

$$ 由此可计算出矩阵的和：F_{n+1}=F_{1}*A^{n-1} $$
所以只用乘上A矩阵的(n-1)次方

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int m,n;
LL a[3][3]={    //预定义A矩阵
  {0,1,0},
  {1,1,1},
  {0,0,1}
};
void mul1(LL c[3],LL a[3],LL b[3][3])   //计算F矩阵乘A矩阵
{
    LL temp[3]={0};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            temp[i]=(temp[i]+a[j]*b[j][i])%m;

    memcpy(c,temp,sizeof temp);
}
void mul2(LL c[][3],LL a[][3],LL b[][3])    //计算A矩阵乘A矩阵
{
    LL 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]+a[i][k]*b[k][j])%m;  

    memcpy(c,temp,sizeof temp);
}
int main()
{
    LL f[3]={1,1,1};
    cin>>n>>m;
    n--;    //计算第n项的和只需要乘n-1次A矩阵，所以n--
    while(n)
    {
        if(n&1) mul1(f,f,a); 
        mul2(a,a,a);
        n>>=1;
    }
    cout<<f[2];
    return 0;
}