Fib数列的递推
矩阵快速幂
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 2
int mod;
#define int long long
struct matrix {
int a[N+2][N+2];
};
matrix m1;
int n;
void init_(matrix &x){
int i,j;
for(i=1;i<=2;i++)
for(j=1;j<=2;j++) {
x.a[i][j]=0;
if(i==j) x.a[i][j]=1;
}
}
matrix mul(matrix &x,matrix &y){
int i,j,k;
matrix z;
for(i=1;i<=2;i++)
for(j=1;j<=2;j++){
z.a[i][j]=0;
for(k=1;k<=2;k++)
z.a[i][j]+=x.a[i][k]*y.a[k][j], z.a[i][j]%=mod;
}
return z;
}
matrix ksm(matrix &x,int k){
matrix tmp=x, ans;
init_(ans);
while(k){
if(k&1) ans=mul(ans,tmp);
tmp=mul(tmp,tmp);
k/=2;
}
return ans;
}
signed main(){
std::ios::sync_with_stdio(0);
cin>>n>>mod;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++) m1.a[i][j]=1;
m1.a[2][2]=0;
if(n<=2){
cout<<1<<endl; return 0;
}
matrix ans =ksm(m1,n-2);
cout<<(ans.a[1][1]+ans.a[2][1])%mod<<endl;
}