问题描述 已知递推公式：
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; }