C++ 代码

//板子题
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct matrix{
    ll c[5][5];
    matrix(){memset(c,0,sizeof c);}
}A,res;
ll n,m;
matrix operator*(matrix&a,matrix&b)
{
    matrix t;
    for(int i=1;i<=3;i++)
    for(int j=1;j<=3;j++)
    for(int k=1;k<=3;k++)
    t.c[i][j]=(t.c[i][j]+a.c[i][k]*b.c[k][j])%m;
    return t;
}
void quickpow(int k)
{
    A.c[1][2]=A.c[2][1]=A.c[2][2]=A.c[2][3]=A.c[3][3]=1;
    res.c[1][1]=res.c[1][2]=res.c[1][3]=1;
    while(k)
    {
        if(k&1)res=res*A;
        A=A*A;
        k>>=1;
    }
}
int main()
{
    cin>>n>>m;
    if(n==1){
        cout<<1%m;
        return 0;
    }
    quickpow(n-1);
    cout<<res.c[1][3];
    return 0;
}