斐波那契数列（求前缀和）（矩阵快速幂）

通项公式：

Sn%m：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3;

int n,m;

void mul(int c[], int a[], int b[][N])
{
	int tmp[N] = {0};
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			tmp[j] = (tmp[j] + (ll)a[i] * b[i][j]) % m;
	
	for(int i=0;i<N;i++) c[i] = tmp[i];
}

void mul(int c[][N], int a[][N], int b[][N])
{
	int tmp[N][N] = {0};
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			for(int k=0;k<N;k++)
				tmp[i][j] = (tmp[i][j] + (ll)a[i][k] * b[k][j]) % m;
	
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			c[i][j] = tmp[i][j];
}

int main()
{
    int f[N] = {1, 1, 1};
    int a[N][N] = {
		{0, 1, 0},
		{1, 1, 1},
		{0, 0, 1}
	};
	scanf("%d%d",&n,&m);
	n--;
	while(n)
	{
		if(n & 1) mul(f, f, a);
		mul(a, a, a);
		n >>= 1;
	}
	printf("%d\n",f[2]);
    return 0;
}

https://blog.csdn.net/Sankkl1/article/details/119685260