试题 算法提高 递推求值

问题描述
　　已知递推公式：

F(n, 1)=F(n-1, 2) + 2F(n-3, 1) + 5,

F(n, 2)=F(n-1, 1) + 3F(n-3, 1) + 2F(n-3, 2) + 3.

初始值为：F(1, 1)=2, F(1, 2)=3, F(2, 1)=1, F(2, 2)=4, F(3, 1)=6, F(3, 2)=5。
　　输入n，输出F(n, 1)和F(n, 2)，由于答案可能很大，你只需要输出答案除以99999999的余数。
输入格式
　　输入第一行包含一个整数n。
输出格式
　　输出两行，第一行为F(n, 1)除以99999999的余数，第二行为F(n, 2)除以99999999的余数。
样例输入
4
样例输出
14

21
数据规模和约定
　　1<=n<=10^18。
思路：矩阵快速幂
矩阵的构造：把已知条件里得元素分解构成矩阵，然后写出矩阵的方程，比如这道题可以如下构造：

可以求得矩阵A={
0,1,1,0,0,0,0,0,
1,0,0,1,0,0,0,0,
0,0,0,0,1,0,0,0,
0,0,0,0,0,1,0,0,
2,3,0,0,0,0,0,0,
0,2,0,0,0,0,0,0,
1,0,0,0,0,0,1,0,
0,1,0,0,0,0,0,1}
然后使用快速幂求解（每道题因为选取的元素不同，最后构造出的矩阵也不相同。）
如何构造矩阵
参考大佬的博客

 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 using namespace std;
 
 typedef long long ll;
 ll mod=99999999;
struct Matrix
{
	ll mat[8][8];
};
       
Matrix fun(Matrix A,Matrix B)//两个矩阵相乘 
{
	Matrix res;
	memset(res.mat,0,sizeof(res.mat));
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<8;j++)
		{
			for(int k=0;k<8;k++)
			{
				res.mat[i][j]=(res.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
			}
		}
	}
	return res;
}

Matrix fun1(ll n)//矩阵快速幂 
{
	Matrix ans,res;
	ans={       0,1,1,0,0,0,0,0,//这里的初始化只能这样写，不能写成ans.mat不然会报错 
                1,0,0,1,0,0,0,0,
                0,0,0,0,1,0,0,0,
                0,0,0,0,0,1,0,0,
                2,3,0,0,0,0,0,0,
                0,2,0,0,0,0,0,0,
                1,0,0,0,0,0,1,0,
                0,1,0,0,0,0,0,1};
    memset(res.mat,0,sizeof(res.mat));
    for(int i=0;i<8;i++)
		res.mat[i][i]=1;//构造单位矩阵 
    while(n)
	{
		if(n%2==1)
			res=fun(res,ans);
		ans=fun(ans,ans);
		n/=2;
	}
	return res;
}
 
 int main()
 {
    ll arr[8]={6,5,1,4,2,3,5,3};
    ll n;
	scanf("%I64d",&n);
	if(n==1)
	  printf("2\n3");
	else if(n==2) 
	  printf("1\n4");
	else if(n==3)
	  printf("6\n5");
	else
	{
		n-=3;//从n>3才开始使用矩阵
		Matrix kk=fun1(n);
		ll sum1=0,sum2=0;
    	for(int i=0;i<8;i++)
	    {
		   sum1=(sum1+arr[i]*kk.mat[i][0])%mod;
		   sum2=(sum2+arr[i]*kk.mat[i][1])%mod;
	    }
	   printf("%I64d\n%I64d",sum1,sum2);	
	}
   return 0; 
 }