C++(clang++ 11.0.1) 解法, 执行用时: 2ms, 内存消耗: 424K, 提交时间: 2022-10-13 21:28:38

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=3;
typedef long long ll;
int n,m;
int a[N][N]={
{0,1,0},
{1,1,1},
{0,0,1}
};
void mul(int a[][N],int b[][N])
{
    int tmp[N][N]={0};
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        for(int k=0;k<N;k++)
        tmp[i][j]=(tmp[i][j]+(ll)a[i][k]*b[k][j])%m;
    memcpy(a,tmp,sizeof tmp);
}
int main()
{
    int f1[N][N]={1,1,1};
    scanf("%d%d",&n,&m);
    n--;
    while(n)
    {
        if(n&1) mul(f1,a);
        mul(a,a);
        n>>=1;
    }
    cout<<f1[0][2]<<endl;
    return 0;
}