题目链接：https://www.dotcpp.com/oj/problem1907.html

    题目分析：

    • 本来以为直接for循环模拟可以过的，但是显示超时了
    • 将快速幂算法扩展为矩阵快速幂，然后求解。

    image.png
    注：但是这个在C语言网上显示运行错误，尚不清楚错哪，逻辑和在本地上运行是正确的。

    1. import java.util.*;
    2. public class Main{
    3.     public static long mod = 99999999;
    4.     public static long[][] fact(long[][] mat, int n){
    5.         if (n == 1){
    6.             return mat;
    7.         }
    8.         long[][] pow = new long[mat.length][mat.length];
    9.         for(int i = 0; i < mat.length; i++){
    10.             for (int j = 0; j < mat.length; j++){
    11.                 pow[i][j] = mat[i][j];
    12.             }
    13.         }
    14.         while(n != 0){
    15.             if((n & 1) == 1){
    16.                 long[][] var = new long[mat.length][mat.length];
    17.                 for(int i = 0; i < mat.length; i++){
    18.                     for (int j = 0; j < mat.length; j++){
    19.                         for (int k = 0; k < mat.length; k++){
    20.                             var[i][j] = (var[i][j] + (mat[i][k] * pow[k][j]) % mod) % mod;
    21.                         }
    22.                     }
    23.                 }
    24.                 for(int i = 0; i < mat.length; i++){
    25.                     for (int j = 0; j < mat.length; j++){
    26.                         mat[i][j] = var[i][j];
    27.                     }
    28.                 }
    29.             }else{
    30.                 long[][] var = new long[mat.length][mat.length];
    31.                 for(int i = 0; i < mat.length; i++){
    32.                     for (int j = 0; j < mat.length; j++){
    33.                         for (int k = 0; k < mat.length; k++){
    34.                             var[i][j] = (var[i][j] + (pow[i][k] * pow[k][j]) % mod) % mod;
    35.                         }
    36.                     }
    37.                 }
    38.                 for(int i = 0; i < mat.length; i++){
    39.                     for (int j = 0; j < mat.length; j++){
    40.                         pow[i][j] = var[i][j];
    41.                     }
    42.                 }
    43.             }
    44.             n >>= 1;
    45.         }
    46.         return mat;
    47.     }
    48.     public static void main(String[] args) {
    50.         Scanner sc = new Scanner(System.in);
    51.         int n = sc.nextInt();
    53.         if(n == 1){
    54.             System.out.println(2);
    55.             System.out.println(3);
    56.         }else if(n == 2){
    57.             System.out.println(1);
    58.             System.out.println(4);
    59.         }else if(n == 3){
    60.             System.out.println(6);
    61.             System.out.println(5);
    62.         }else{
    63.             long[] v = {6, 5, 1, 4, 2, 3, 1};
    64.             long[][] mat = {{0, 1, 1, 0, 0, 0, 0},
    65.                             {1, 0, 0, 1, 0, 0, 0},
    66.                             {0, 0, 0, 0, 1, 0, 0},
    67.                             {0, 0, 0, 0, 0, 1, 0},
    68.                             {2, 3, 0, 0, 0, 0, 0},
    69.                             {0, 2, 0, 0, 0, 0, 0},
    70.                             {5, 3, 0, 0, 0, 0, 1}};
    71.             long[][] mat2 = fact(mat, n - 3);
    72.             long[] ans = new long[2];
    73.             for(int k = 0; k < 2; k++){
    74.                 long temp = 0;
    75.                 for(int i = 0; i < v.length; i++){
    76.                     temp = (temp + (v[i] * mat[i][k]) % mod) % mod;
    77.                 }
    78.                 ans[k] = temp;
    79.             }
    80.             System.out.println(ans[0]);
    81.             System.out.println(ans[1]);
    82.         }
    83.     }
    84. }