巧妙的矩阵构造

Fn= [fn,fn+1,sn]
Fn+1= [fn+1,fn+2,sn+1]
Fn*A = Fn+1
可求得A = 0 1 0
1 1 1
0 0 1
Fn = F1 * $A^{n-1}$

F1 = 1 1 1
0 0 0
0 0 0
求得Fn F[0][2]就是答案

#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 3;
LL n,m;
void mul(LL c[][N],LL a[][N],LL b[][N])//多维数组除了第一维 其他都要指定长度
{
    LL temp[N][N]={0};
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            for(int k=0;k<N;++k)
            {
                temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%m;
            }
        }
    }
    memcpy(c,temp,sizeof temp);//形参sizeof 是不可行的
}
int main()
{
    cin>>n>>m;
    LL f[N][N]={1,1,1};
    LL a[N][N]={
        {0,1,0},
        {1,1,1},
        {0,0,1}
    };
    n--;
    while(n)
    {
        if(n&1)mul(f,f,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<<f[0][2]<<endl;
    return 0;
}