AcWing 1304. 佳佳的斐波那契（数学、矩阵快速幂）

#include<bits/stdc++.h>
using namespace std;
const int N=4;
#define ll long long
ll n,mod;
ll a[][N]={
    {0,1,0,0},
    {1,1,1,0},
    {0,0,1,1},
    {0,0,0,1}
};
void mul(ll a[],ll b[],ll c[][N]){
    ll tep[N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
                tep[i]=(tep[i]+b[j]*c[j][i]%mod)%mod;
            }
    }
    memcpy(a,tep,sizeof tep);
}
void mul(ll a[][N],ll b[][N],ll c[][N]){
    ll tep[N][N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                tep[i][j]=(tep[i][j]+b[i][k]*c[k][j]%mod)%mod;
            }
        }
    }
    memcpy(a,tep,sizeof tep);
}
int main(){
    cin>>n>>mod;
    ll ans[N]={0,1,0,0};
    ll k=n;
    while(n){
        if(n&1)mul(ans,ans,a);
        mul(a,a,a);
        n>>=1;
        /*for(int i=0;i<N;i++){
            cout<<ans[i]<<" ";
        }
        cout<<endl;*/
    }
    cout<<(k*ans[N-2]%mod-ans[N-1]+mod)%mod<<endl;
    
    
}