算法提高递推求值 (矩阵快速幂)

淩亂°似流年 2022-09-28 11:58 173阅读 0赞

问题描述

已知递推公式：  
  
　　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的余数。

样例输入

样例输出

14  
  
21

数据规模和约定

1<=n<=10^18。

题解：1<=n<=10^18，直接暴力递归显然会T。所以只能构造矩阵，用矩阵快速幂了。

构造一个1 x 8矩阵：

![gif.latex_28_20f_28n-1_2C1_29_2Cf_28n-1_2C2_29_2Cf_28n-2_2C1_29_2Cf_28n-2_2C2_29_2Cf_28n-3_2C1_29_2Cf_28n-3_2C2_29_2C5_2C3_20_29][]

我们要通过上面这个矩阵乘以一个8 x 8的矩阵A得出一个新矩阵：

![gif.latex_28_20f_28n_2C1_29_2Cf_28n_2C2_29_2Cf_28n-1_2C1_29_2Cf_28n-1_2C2_29_2Cf_28n-2_2C1_29_2Cf_28n-2_2C2_29_2C5_2C3_20_29][]

逆推计算得到矩阵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<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod=99999999;
    struct matrix
    {
    	ll a[8][8];
    };
    matrix multiply(matrix x,matrix y,int m,int n,int s)
    {
    	matrix tmp;
    	memset(tmp.a,0,sizeof(tmp.a));
    	for(int i=0;i<m;i++){
    		for(int j=0;j<n;j++){
    			for(int k=0;k<s;k++){
    				tmp.a[i][j]=(tmp.a[i][j] + (x.a[i][k] * y.a[k][j])%mod)%mod;
    			}
    		}
    	}
    	return tmp;
    }
    matrix tmp={
                    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
                };
    int main()
    {	
        matrix res;
        ll f[8]={6,5,1,4,2,3,5,3};
        ll sum1,sum2,n;
        memset(res.a,0,sizeof(res.a));
        for(int i=0;i<8;i++){
        	res.a[i][i]=1;
    	}
    	cin>>n;
        if(n==1)
            cout<<"2"<<endl<<"3"<<endl;
        if(n==2)
            cout<<"1"<<endl<<"4"<<endl;
        if(n==3)
            cout<<"6"<<endl<<"5"<<endl;
        if(n>=4){
        	n-=3;
        	while(n) //矩阵快速幂 
        	{
        		if(n&1)	res=multiply(res,tmp,8,8,8);
        		n>>=1;
        		tmp=multiply(tmp,tmp,8,8,8);
    		}
    		sum1=0;
    		sum2=0;
    		for(int i=0;i<8;i++)
    		{
    			sum1=(sum1+(f[i]*res.a[i][0])%mod)%mod;
    			sum2=(sum2+(f[i]*res.a[i][1])%mod)%mod;
    		}
    		cout<<sum1<<endl;
    		cout<<sum2<<endl;
    	}
    	return 0;
    }

[gif.latex_28_20f_28n-1_2C1_29_2Cf_28n-1_2C2_29_2Cf_28n-2_2C1_29_2Cf_28n-2_2C2_29_2Cf_28n-3_2C1_29_2Cf_28n-3_2C2_29_2C5_2C3_20_29]: /images/20220708/269b2050d5eb4a019b3fb67fcaae2b7c.png
[gif.latex_28_20f_28n_2C1_29_2Cf_28n_2C2_29_2Cf_28n-1_2C1_29_2Cf_28n-1_2C2_29_2Cf_28n-2_2C1_29_2Cf_28n-2_2C2_29_2C5_2C3_20_29]: /images/20220708/7784e2adb4954c9f8361ba99f9d5dc85.png