题目链接：

斐波那契数列卷积


示例1
输入

3

输出

2

示例2
输入

19260817

输出

511682927

解题思路

提前我们要知道 Fn=Fn-1+Fn-2
规律是适合的，因为写起来太麻烦所以这就举个例子说明吧，
A7= F0* F7 + F1* F6 + F2* F5 + F3* F4 + F4* F3 + F5* F2 + F6* F1 + F7* F0
A6= F0* F6 + F1* F5 + F2* F4 + F3* F3 + F4* F2 + F5* F1 + F6* F0
A7-A6=F0*(F7-F6) + F1*(F6-F5) + F2*(F5-F4) + F3*(F4-F3) + F4*(F3-F2) + F5*(F2-F1) + F6*(F1-F0) + F7* F0
因为 F1=1,F0=0；所以F6*(F1-F0)=F6；
A7-A6=F0* F5 + F1* F4 + F2* F3 + F3* F2 + F4* F1 + F5* F0 + F6
A7-A6=A5+F6；
也就是 An=An-1+An-2+Fn-1
这样就可以用矩阵快速幂来构造一个矩阵来求了（感谢bly提供的方程，tql）

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;

struct node{
	ll a[4][4];
};

node mul(node a,node b)
{
	node ans;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			ans.a[i][j]=0;
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			for(int k=0;k<4;k++)
			{
				ans.a[i][j]=(ans.a[i][j]+((a.a[i][k]%mod)*(b.a[k][j]%mod))%mod)%mod;
			}
		}
	}
	return ans;
}

node poww(node a,ll b)
{
	node ans;
	memset(ans.a,0,sizeof(ans.a));
	for(int i=0;i<4;i++)	ans.a[i][i]=1;
	while(b)
	{
		if(b&1)	ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}

node yl,bly;

int main()
{
	ios::sync_with_stdio(0);
	ll n;
	cin>>n;
	memset(yl.a,0,sizeof(yl.a));
	memset(bly.a,0,sizeof(bly.a));
	yl.a[0][0]=1;
	yl.a[0][1]=1;
	yl.a[0][2]=1;
	yl.a[1][0]=1;	
	yl.a[2][2]=1;
	yl.a[2][3]=1;
	yl.a[3][2]=1;
	bly.a[2][0]=1;
	bly.a[0][0]=1;
	bly.a[3][0]=1;
	if(n==1)	cout<<0<<endl;
	else if(n==2)	cout<<1<<endl;
	else
	{
		node ans=poww(yl,n-2);
		ans=mul(ans,bly);
		cout<<ans.a[0][0]<<endl;
	}
	return 0;
}