AcWing 1303. 斐波那契前 n 项和

#include<bits/stdc++.h>
#define LL long long
#define N 3
using namespace std;
int n,m;
void cal(int c[],int a[],int b[][N])
{
    int temp[N]={0};
    for (int i=0; i<N;i++)
        for (int j=0;j<N;j++)
            temp[i]=(temp[i]+(LL)a[j]*b[j][i])%m;
    memcpy(c, temp, sizeof temp);
}
void mul(int c[][N], int a[][N], int b[][N])
{
    int 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]+(LL)a[i][k]*b[k][j]) % m;
    memcpy(c, temp, sizeof temp);
}
int main()
{
    cin >>n>>m;
    int f1[N]={1,1,1};
    int a[N][N]={0,1,0,1,1,1,0,0,1};
    n--;
    while (n)
    {
        if (n&1)cal(f1,f1,a);
        mul(a,a,a);
        n>>=1;
    }
    cout<<f1[2];
    return 0;
}