ac

假设农场中成熟的母牛每年只会生 1 头小母牛，并且永远不会死。第一年农场中有一只成熟的母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 n，求出 n 年后牛的数量。

第1年：f(1)        = 1
第2年：f(2) = f(1) + 1 = 2
第3年：f(3) = f(2) + 1 = 3

第4年：f(4) = f(3) + 1 = 4 // 计算f4时只有1头成年
第5年：f(5) = f(4) + 2 = 6 // 计算f5时有2头成年
第6年：f(6) = f(5) + 3 = 9 // 计算f6时有3头成年

f(n) = f(n-1) + f(n-3)

                                         1  1  0
[fn, fn-1, fn-2] = [fn-1, fn-2, fn-3] *  0  0  1
                                         1  0  0


[fn, fn-1, fn-2] = [f3, f2, f1] * Matrix^(n-3) = [3,2,1] * Matrix^(n-3)

快速幂求解

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int mod=(int)Math.pow(10,9)+7;

    public static void main(String[] args) throws Exception {
        long n = sc.nextLong();
        System.out.println(fab(n));
//        for(int i=1;i<=20;i++) {
//            System.out.println(i + " " + fab(i));
//        }
    }

    // [fn fn-1] = [f1 f0] * matrix^(n-1)
    static long fab(long n){
        if(n == 0){
            return 0;
        }
        if(n >= 1 && n <= 3){
            return n;
        }
        // 快速幂求 matrix^(n-1)
        long[][] res = {
                {1,0,0},
                {0,1,0},
                {0,0,1}
        };
        long[][] matrix = {
                {1,1,0},
                {0,0,1},
                {1,0,0}
        };
        long m = n - 3;
        while (m != 0){
            if((m & 1) == 1){
                res = multi(res, matrix);
            }
            matrix = multi(matrix, matrix);
            m = m >> 1;
        }
        // 求fn
        long fn = (3 * res[0][0] + 2 * res[1][0] +  1 * res[2][0]) % mod;
        return fn;
    }

    static long[][] multi(long[][] m1, long[][] m2){
        int n = 3;
        long[][] m = new long[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                long sum = 0;
                for(int k=0;k<n;k++){
                    sum += m1[i][k] * m2[k][j] % mod;
                }
                m[i][j] = sum % mod;
            }
        }
        return m;
    }
}
/*
6

9
 */