题解
代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<cstring>
typedef long long LL;
int F[3]={1,1,1},n,m;
int A[3][3]={
{0,1,0},
{1,1,1},
{0,0,1}
};
void mul(int a[],int b[][3],int c[]){//a*b->c
int t[3]={0};
for(int j=0;j<3;j++){
for(int i=0;i<3;i++){
t[j]=(t[j]+(LL)a[i]*b[i][j])%m;
}
}
copy(t,t+3,a);//copy(source_begin,source_end,dst_begin)
}
void mul(int a[][3],int b[][3],int c[][3]){//a*b->c
int t[3][3]={0};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
t[i][j]=(t[i][j]+(LL)a[i][k]*b[k][j])%m;
}
}
}
memcpy(c,t,sizeof t);//memcpy(dst,source,size)
}
int main(void){
cin>>n>>m;
n--;
while(n){//矩阵快速幂
if(n&1) mul(F,A,F);
mul(A,A,A);
n>>=1;
}
cout<<F[2];
}