ADV-218繰返し値

ADV-218繰返し値
問題の説明
既知の繰返し式:
　　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)を入力します.答えが大きい可能性がありますので、999999999の残りを出力するだけです.
入力フォーマット
最初の行に整数nが含まれていることを入力します.
出力フォーマット
2行出力し、第1行F(n,1)を99999999の剰余、第2行F(n,2)を9999999999の剰余で割る.
サンプル入力
4
サンプル出力
14
21
データ規模と約定
　　1<=n<=10^18
テーマ分析
行列乗算を実現する方法と行列の高速べき乗を実現する方法を書き,行列で繰返し関係式を表し,初期値に注意する.
JAva実装

import java.util.Scanner;

public class Main {
    final static int mod = 99999999;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if (n == 1) {
            System.out.println(2);
            System.out.println(3);
        }else if(n == 2){
            System.out.println(1);
            System.out.println(4);          
        }else if(n == 3){
            System.out.println(6);
            System.out.println(5);          
        }else{
            long[][]a = {{0,1,0,0,2,0,5},
                         {1,0,0,0,3,2,3},
                         {1,0,0,0,0,0,0},
                         {0,1,0,0,0,0,0},
                         {0,0,1,0,0,0,0},
                         {0,0,0,1,0,0,0},
                         {0,0,0,0,0,0,1}};
            long[][]b = {{6},{5},{1},{4},{2},{3},{1}};
            long[][]x = Multiply_Matrix(Multiply_ksm(a, n-3), b);
            long result1 = x[0][0]%mod;
            long result2 = x[1][0]%mod;
            System.out.println(result1);
            System.out.println(result2);
        }
        sc.close();
    }
    public static long[][] Multiply_Matrix(long[][] a, long[][] b) {
        long[][] c = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                long temp = 0;
                for (int k = 0; k < b.length; k++) {
                    temp = (temp + ((a[i][k] % mod) * (b[k][j] % mod)) % mod) % mod;
                }
                c[i][j] = temp;
            }
        }
        return c;
    }
    public static long[][] Multiply_ksm(long[][] a, long k) {
        long[][] d = new long[a.length][a[0].length];
        if (k == 1) {
            return a;
        } else if (k == 2) {
            return Multiply_Matrix(a, a);
        } else if (k % 2 == 0) {
            d = Multiply_ksm(Multiply_Matrix(a, a), k / 2);
            return d;
        } else {
            d = Multiply_ksm(Multiply_Matrix(a, a), k / 2);
            return Multiply_Matrix(d, a);
        }
    }
}