输出斐波那契数列前 n 项和 对m取摸的结果
#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;
}