C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 416K, 提交时间: 2022-11-17 00:24:26

#include<bits/stdc++.h>
#define endl '\n'
#define rep(i,a,b) for (int i=a;i<b;++i)
#define per(i,a,b) for (int i=a;i>b;--i)
using namespace std;
int n,m;
void mul(int a[4][4],int b[4][4])
{
    int c[4][4]={0};
    rep(i,0,4)
    rep(j,0,4)
    rep(k,0,4){
        c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%m;
    }
    rep(i,0,4) rep(j,0,4) a[i][j]=c[i][j];
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int f[4][4]={1,1,1,0};
    int a[4][4]={
        0,1,0,0,
        1,1,1,0,
        0,0,1,1,
        0,0,0,1
                 };
    int k=n-1;
    while(k){
        if(k&1) mul(f,a);
        mul(a,a);
        k>>=1;
    }
    cout<<((1ll*n*f[0][2]-f[0][3])%m+m)%m;
    return 0;
}

C++(clang++11) 解法, 执行用时: 5ms, 内存消耗: 500K, 提交时间: 2021-03-05 19:50:22

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int N, M;
struct mat{
    int a[2][2];
    mat operator*(mat t){
        mat r;
        memset(r.a,0,16);
        fo(i,0,2)fo(k,0,2)fo(j,0,2)r.a[i][j]=(r.a[i][j] +1ll*a[i][k]*t.a[k][j])%M;
        return r;
    }//矩阵结构体里重载矩阵乘法
}o,t;
int main(){
    cin>>N>>M;
    t.a[0][0] = t.a[1][1] = 1;
    o.a[0][0] = o.a[1][0] = o.a[0][1] = 1;
    for (int i=N+2;i;i>>=1,o=o*o) if (i&1) t = t * o;
    printf( "%lld\n", ( 1ll * N * t.a[0][1] + M - t.a[0][0] + 2 ) % M );
    return 0;
}