算法提高 遞推求值 時間限制：1.0s 內(nèi)存限制：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的余數(shù)。輸入格式輸入第一行包含一個整數(shù)n。輸出格式輸出兩行，第一行為F(n, 1)除以99999999的余數(shù)，第二行為F(n, 2)除以99999999的余數(shù)。樣例輸入4樣例輸出1421數(shù)據(jù)規(guī)模和約定1<=n<=10^18。 package com.sihai.improve; import java.util.Scanner;public class sihai{public final static long[][] UNIT = {{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},{0,1,0,0,0,0,1,0},{1,0,0,0,0,0,0,1}}; //根據(jù)遞推公式構(gòu)造的矩陣public final static long[][] ZERO = new long[8][8]; //元素全為0public final static long p = 99999999L;//獲取矩陣NUIT的n次方結(jié)果public long[][] getNofMatrix(long n) {if(n == 0)return ZERO;if(n == 1)return UNIT;if((n & 1) == 0) { //當(dāng)n為偶數(shù)時long[][] matrix = getNofMatrix( n >> 1);return multiOfMatrix(matrix, matrix);} //當(dāng)n為奇數(shù)時long[][] matrix = getNofMatrix((n - 1) >> 1);return multiOfMatrix(multiOfMatrix(matrix, matrix), UNIT);}//計算矩陣A*B取余99999999的值public long[][] multiOfMatrix(long[][] A, long[][] B) {long result[][] = new long[A.length][B[0].length];for(int i = 0;i < A.length;i++) {for(int j = 0;j < B[0].length;j++) {for(int k = 0;k < A[0].length;k++)result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % p;}}return result;}public void printResult(long n) {long[][] start = {{6,5,1,4,2,3,3,5}};if(n == 1) {System.out.println(start[0][4]+"\n"+start[0][5]);return;} else if(n == 2) {System.out.println(start[0][2]+"\n"+start[0][3]);return;} else if(n == 3) {System.out.println(start[0][0]+"\n"+start[0][1]);return;}long[][] A = getNofMatrix(n - 3);start = multiOfMatrix(start, A);System.out.println(start[0][0]+"\n"+start[0][1]);return;}public static void main(String[] args) {Main test = new Main();Scanner in = new Scanner(System.in);long n = in.nextLong();test.printResult(n);} }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯-递推求值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。