斐波那契数列前n项和 (矩阵乘法)

公式：(f(n+2)-f(1))
但是本题求的是前n+1项的和，所以计算f(n+3)-f(1)
做法：矩阵乘法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
// #include<unordered_map>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i) 
#define px first
#define py second  
typedef long long ll;
typedef pair<int,int>PII;
const int N = 2e5 + 10;
const ll mod = 998244353;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//

struct mat{
	ll m[3][3];				//这里是矩阵大小
	mat(){memset(m,0,sizeof(m));}
};

mat mul(mat x,mat y){	//矩阵乘法
	mat res;
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j)
			for(int k=0;k<3;++k)
				res.m[i][j]=(res.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
	return res;
}

mat power(mat A, ll n){	//矩阵快速幂
	mat c=A, res;
	for(int i=0;i<3;++i) res.m[i][i]=1;	//注意res是单位阵
	while(n){
		if(n&1) res=mul(res,c);
		c=mul(c,c);
		n>>=1;
	}
	return res;
}

ll n;

int main()
{
    scanf("%lld",&n);
    mat A, B, C;
	A.m[0][0] = 1, A.m[0][1] = 1, A.m[1][0] = 1;
	B.m[0][0] = 0, B.m[1][0] = 1;
    C=mul(power(A,n + 3) , B);
    ll res = (C.m[0][0] - 1 + mod) % mod;
    printf("%lld
",res);
    return 0;
}