Sum of the first n terms of Fibonacci (fast power of matrix)

analysis ： From the properties of Fibonacci sequence, we can get the following recurrence formula , Using this recursive formula, we can use the fast power of the matrix to quickly find sn

  The thing to notice is when n=1 Just give it a special judgment ,[fn-1,fn,sn]=[f1,f1,s2]* Recursive matrix n-2 Power , Then take out. sn The elements are , It will explode in the process int, So we have to drive longlong And in the process m modulus

Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
int n,m;
void mul(ll ans[][4],ll a[][4],ll b[][4])
{
	ll t[4][4]={0};
	for(int i=1;i<=3;i++)
	for(int j=1;j<=3;j++)
	for(int k=1;k<=3;k++)
	{
		t[i][j]+=a[i][k]*b[k][j];
		t[i][j]%=m;
	}
	memcpy(ans,t,sizeof t);
}
int main()
{
	cin>>n>>m;
	if(n==1) printf("%d",1%m);
	else
	{
		ll t[4][4]={
		{0,0,0,0},
		{0,0,1,1},
		{0,1,1,1},
		{0,0,0,1}
		};
		ll ans[4][4]={
		{0,0,0,0},
		{0,1,0,0},
		{0,0,1,0},
		{0,0,0,1}
		};
		n-=2;
		while(n)
		{
			if(n&1) mul(ans,ans,t);
			n>>=1;
			mul(t,t,t);
		}
		printf("%lld",(ans[1][3]+ans[2][3]+2*ans[3][3])%m);
	}
	return 0;
}