算法提高 递推求值

问题描述 　　已知递推公式：

　　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。 解题思路 可模仿矩阵快速幂在斐波拉契数列上的应用，构造一下矩阵。 [f(n,1),f(n,2),f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),5,3] = [f(n-1,1),f(n-1,2),f(n-2,1),f(n-2,2),f(n-3,1),f(n-3,2),5,3] * A 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 注意！重要数据请用 long long 类型 #include <iostream> #include <cstdio> #include <vector> using namespace std;const int mod = 99999999; vector<long long>c[8]; vector<long long>t[8]; vector<long long>res[8]; long long f[8]={6,5,1,4,2,3,5,3};void init(){int i;for(i=0;i<8;i++){c[i].assign(8,0);t[i].assign(8,0);res[i].assign(8,0);}t[0][1]=1;t[0][2]=1;t[1][0]=1;t[1][3]=1;t[2][4]=1;t[3][5]=1;t[4][0]=2;t[4][1]=3;t[5][1]=2;t[6][0]=1;t[6][6]=1;t[7][1]=1;t[7][7]=1; }void mul(vector<long long>a[], vector<long long>b[]){int i,j,k;for(i=0;i<8;i++){for(j=0;j<8;j++){c[i][j] = 0;for(k=0;k<8;k++){c[i][j] = (c[i][j]+(a[i][k]*b[k][j])%mod)%mod; }}} }void QuickPow(long long n){int i;for(i=0;i<8;i++)res[i][i]=1;while(n){if(n & 1){mul(t, res);for(i=0;i<8;i++)res[i].swap(c[i]);}mul(t, t);for(i=0;i<8;i++)t[i].swap(c[i]);n = n>>1;} }int main() {init();long long n;long long sum1=0,sum2=0;cin>>n;if(n==1)cout<<"2"<<endl<<"3"<<endl;else if(n==2)cout<<"1"<<endl<<"4"<<endl;else if(n==3)cout<<"6"<<endl<<"5"<<endl;else{n-=3;QuickPow(n);for(int i=0;i<8;i++){sum1=(sum1+(f[i]*res[i][0])%99999999)%99999999;sum2=(sum2+(f[i]*res[i][1])%99999999)%99999999;} cout<<sum1<<endl<<sum2<<endl;}return 0; }

 

转载于:https://www.cnblogs.com/woxiaosade/p/10297585.html

总结

以上是生活随笔为你收集整理的算法提高 递推求值的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。