佳佳的斐波那契（数学推导+构造+矩阵快速幂）

**构造矩阵****

已知：
f[n+1]=f[n]+f[n-1];
T[n]=f[1]+2*f[2]+3*f[3]+······+n*f[n];
S[n]=f[1]+f[2]+f[3]+······+f[n];
求出T[n]

令P[n]=n*S[n]-T[n];
（1）P[n]=n*S[n]-T[n]=(n-1)*f[1]+(n-2)*f[2]+(n-3)*f[3]+······+f[n-1];
（2）P[n+1]=n*f[1]+(n-1)*f[2]+(n-2)*f[3]+······+f[n];
由第2个式子减去第1个式子可得p[n+1]-p[n]=S[n];
据以上信息可得以下关系：
f[n+1]=f[n]+f[n-1];
S[n+1]=S[n]+f[n+1];
P[n+1]=P[n]+S[n];
构造矩阵:Fn={f[n],f[n+1],S[n],P[n]};
Fn+1={f[n+1],f[n+2],S[n+1],P[n+1]};
假象出一个常数矩阵A;
A*fn=fn+1;
A={
    {0,1,0,0},
    {1,1,1,0},
    {0,0,1,1},
    {0,0,0,1}
};
构造矩阵完毕，接着根据Fn=f1*A^(n-1),可求出Fn,至于A^(n-1)利用矩阵快速幂可将其解决
求Tn,Tn=n*S[n]-P[n];
特别注意：需要强制转换为long long ，有许多地方都会爆int

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=4;
int n,m;
void mul(int c[][N],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(c,tmp,sizeof tmp);
}
int main()
{
    cin>>n>>m;
    int F1[4][4]={1,1,1,0};
    int A[4][4]={
        {0,1,0,0},
        {1,1,1,0},
        {0,0,1,1},
        {0,0,0,1}
    };
    int k=n-1;
    while(k)
    {
        if(k&1) mul(F1,F1,A);
        mul(A,A,A);
        k>>=1;
    }
    cout<<(((ll)n*F1[0][2]-F1[0][3])%m+m)%m<<endl;
    return 0;
}