acwing1303. 斐波那契前 n 项和

题目

题解

[fn,fn+1,sn]*A=f[n+1,fn+2,sn+1]
其中A={
{0,1,0},
{1,1,1},
{0,0,1}
}

#include<iostream>
#include<cstring>
using namespace std;
const int N=3;
int n,m;
void mult(int c[],int a[],int b[][N]){
    int temp[N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            temp[i]=(temp[i]+(long long)a[j]*b[j][i])%m;
        }
    }
    memcpy(c,temp,sizeof temp);
}
void mult(int c[][N],int a[][N],int b[][N]){
    int temp[N][N]={0};
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                temp[i][j]=(temp[i][j]+(long long)a[i][k]*b[k][j])%m;
            }
        }
    }
    memcpy(c,temp,sizeof temp);
}
int main(){
    cin>>n>>m;
    int f[N]={1,1,1};
    int A[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n){
        if(n&1)mult(f,f,A);//f1,f2,s1
        mult(A,A,A);
        n>>=1;
    }
    cout<<f[2]<<endl;
    return 0;
}

`