AcWing 1303. 斐波那契前 n 项和 (矩阵快速幂）

5 1000

12

#include<bits/stdc++.h>
using namespace std;
const int N=3;
#define ll long long
ll n,mod;
ll a[][N]={
    {0,1,0},
    {1,1,1},
    {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};
    while(n){
        if(n&1)mul(ans,ans,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<<ans[2]<<endl;
    
    
}