LOJ #10221. 「一本通 6.5 例 3」Fibonacci 前 n 项和

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

long long n,Mod;

struct no {
	long long a[5][5];
} ans,x;

no mul(no &x,no &y) {
	no c;
	memset(&c,0,sizeof(c));
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++)
			for(int k=1; k<=3; k++)
				c.a[i][j]=(c.a[i][j]+x.a[i][k]*y.a[k][j]%Mod);
	return c;
}

void work(long long n) {
	while(n) {
		if(n&1)
			ans=mul(ans,x);
		x=mul(x,x);
		n>>=1;
	}
}

int main () {
	ans.a[1][1]=ans.a[2][2]=ans.a[3][3]=1;
	x.a[1][1]=1;
	x.a[1][2]=1;
	x.a[1][3]=0;
	x.a[2][1]=0;
	x.a[2][2]=1;
	x.a[2][3]=1;
	x.a[3][1]=0;
	x.a[3][2]=1;
	x.a[3][3]=0;
	scanf("%lld%lld",&n,&Mod);
	work(n-1);
	printf("%lld\n",(ans.a[1][1]+ans.a[1][2]+ans.a[1][3])%Mod);
	return 0;
}