ac

给出一个整数 n，代表台阶数，一次可以跨 2 个或者 1 个台阶，请输出有多少种走法。

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=0;i<=20;i++) {
//            System.out.print(" " + fab(i));
//        }
    }

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

    static long[][] multi(long[][] m1, long[][] m2){
        int n = 2;
        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;
    }
}
/*
3

3
 */