Java实现蓝桥杯算法提高递推求值

算法提高递推求值

时间限制：1.0s 内存限制：256.0MB

问题描述

　　已知递推公式：

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。

import java.util.Scanner;

public class 递推求值 {

	static final int mod=99999999;

	static long num[]=new long[] {6,5,1,4,2,3,1};

	static long n,ans1,ans2;

	static class Matrix{

		long mat[][]=new long[7][7];

		Matrix multi(Matrix a) {       //矩阵乘法

			Matrix rec=new Matrix();

			for(int i=0;i<7;i++) {

				for(int k=0;k<7;k++) {

					if(this.mat[i][k]!=0)

						for(int j=0;j<7;j++) {

							rec.mat[i][j]=(rec.mat[i][j]+(this.mat[i][k]*a.mat[k][j])%mod)%mod;

						}

				}

			}

			return rec;

		}

	}

	//ST表示该方阵，E表示单位矩阵（其地位相当于整数1）

	static Matrix ST=new Matrix(),E=new Matrix();

	static void init() {      //初始化

		for(int i=0;i<7;i++)

			E.mat[i][i]=1;

		ST.mat[0][1]=1;ST.mat[0][4]=2;ST.mat[0][6]=5;

		ST.mat[1][0]=1;ST.mat[1][4]=3;ST.mat[1][5]=2;ST.mat[1][6]=3;

		ST.mat[2][0]=1;

		ST.mat[3][1]=1;

		ST.mat[4][2]=1;

		ST.mat[5][3]=1;

		ST.mat[6][6]=1;

	}

	static Matrix matrix_pow(long n) { //矩阵快速幂

		Matrix rec=E,base=ST;

		while(n!=0) {

			if(n%2==1) {

				rec=rec.multi(base);

			}

			base=base.multi(base);

			n=n>>1;

		}

		return rec;

	}

	public static void main(String[] args) {

		Scanner cin=new Scanner(System.in);

		n=cin.nextLong();

		if(n<4) {

			int index=(int)(3-n)*2;

			System.out.println(num[index]);

			System.out.println(num[index+1]);

		}else {

			init();

			ST=matrix_pow(n-3);

			for(int i=0;i<7;i++) {

				ans1=(ans1+(ST.mat[0][i]*num[i])%mod)%mod; //求F(n,1)

				ans2=(ans2+(ST.mat[1][i]*num[i])%mod)%mod; //求F(n,2)

			}

			System.out.println(ans1);

			System.out.println(ans2);

		}

	}

}

巴特西

Java实现蓝桥杯算法提高递推求值

最新文章

热门文章

巴特西

Java实现 蓝桥杯 算法提高 递推求值

最新文章

热门文章

Java实现蓝桥杯算法提高递推求值