130 0左边必有1的二进制字符串的数量

显然最高位置必须时1，应该时每个0左边必须有1，即只能出现10，11，而不能出现00，01

p(i) 为 0...i-1 的位置已经确定，这一段符合要求(第i-1个位置的字符为1时)如果穷举i～N-1位置上的所有情况会产生多少种符合要求的字符串

i < n-1 时 p(i) = p(i+1) + p(i+2)
i = n-1 时 p(i) = 2
i = n 时，p(i) = 1

前2位	第三位
11	0 或 1都可以
10	只能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 long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception {
       int n = sc.nextInt();
       System.out.println(getNth(n+1));
    }

    static long getNth(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        long[][] rsMatrix = {
                {1,0},
                {0,1}
        };;
        long[][] matrixFun = {
                {1,1},
                {1,0}
        };;
        // 快速幂 如n=5, 求funMatrix^5 即 funMatrix^101 = funMatrix^4 * funMatrix^1
        n = n - 2;
        while (n != 0){
            int bit = n & 1;
            if(bit == 1){
                rsMatrix = multiMatrix(rsMatrix, matrixFun);
            }
            matrixFun = multiMatrix(matrixFun, matrixFun);
            n = n >> 1;
        }
        long ans = (rsMatrix[0][0] + rsMatrix[1][0]) % mod;
        return ans;
    }

    // 0矩阵
    static long[][] zeroMatrix = {
            {0,0},
            {0,0}
    };

    // 1矩阵
    static long[][] oneMatrix = {
            {1,0},
            {0,1}
    };

    // 递推矩阵
    static long[][] funMatrix = {
            {1,1},
            {1,0}
    };

    // 矩阵乘法
    static long[][] multiMatrix(long[][] m1, long[][] m2){
        long[][] m = {
                {0,0},
                {0,0}
        };
        for(int i = 0;i < 2;i++){
            for(int j=0;j<2;j++){
                long tmp = 0;
                for(int k=0;k<2;k++){
                    tmp += (m1[i][k] * m2[k][j]);
                    tmp %= mod;
                }
                m[i][j] = tmp;
            }
        }
        return m;
    }

}
/*
fn，fn-1 = (fn-1, fn-2) * fmatrix
*/

ac