本文共 1491 字，大约阅读时间需要 4 分钟。

分析

令

$$\begin{array}{llc}& A=& \left[\begin{array}{ccc}0& 1& 0\\ 1& 1& 1\\ 0& 0& 1\end{array}\right]\end{array}$$

$$由此可计算出矩阵的和：F_{n+1}=F_1\ast A^{n-1}$$

输入样例

25000 100000

输出样例

84375

(计算第25000项的斐波那契数列的总和对100000取模后的结果)

C++ 代码

#include
   
    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<