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

#include <stdio.h>

#define MOD 0x20000000

int main(void) {
    int n;
    scanf("%d", &n);
    if (n == 1) {
        printf("%d\n", 1);
        return 0;
    }
    int next1 = 2, next2 = 1, tmp;
    n -= 2;
    while (n-- > 0) {
        tmp = (next1 + next2) % MOD;
        next2 = next1;
        next1 = tmp;
    }
    printf("%d\n", next1);
    return 0;
}

设f(i)表示长度为i的【0左边必有1的二进制字符串的数量】：

• 先确定第一个字符，显然首个字符必须为1（如果为0则左边没有1给它靠了），所以f(1) = 1；
• 第二个字符既可以为0也可以为1，即10和11两个，所以f(2) = 2；
• 如果第二个字符选了0（即前两位是10），那么第三个字符只能是1即101（因为0的左边必须紧挨着一个1，所以没得选）；如果第二个字符选了1（即前两位是11），那么第三个字符既可以是0也可以是1（110或111），所以f(3) = 1+2 = 3；

import java.util.Scanner;

public class Main {

    public static final int MOD = 1 << 29;

    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        System.out.println(getCount(n));
    }

    public static int getCount(int n) {
        if (n <= 2) {
            return n;
        }
        int a = 1, b = 2; // f(1) = 1, f(2) = 2

        for (int i = 3; i <= n; i++) {
            int tmp = (a + b) % MOD;
            a = b;
            b = tmp;
        }
        return b;
    }
}

func main() {    
    n := 0
    fmt.Scan(&n)
    if n == 1 {
        fmt.Println(1)
        return
    } else if n == 2 {
        fmt.Println(2)
        return
    }
    var a, b, res int64
    a, b = 1, 2
    for i := 3; i <= n; i++ {
        res = (a + b) % int64(math.Pow(2, 29))
        a = b
        b = res
    }
    fmt.Println(res)
}

import java.util.*;

public class Main{
    public static final int mod = (int) Math.pow(2, 29);
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(getMaxNum(n));
    }
    
   /*假设p(i)表示0~i-1位置上的字符已经确定，这一段符合要求且第
    i-1位上是'1',接下来i~n-1位置上进行穷举看有多少个字符串符合条件。
    p(n-1)表示n-2位为1且之前已经定好了，最后一位只有两种可能，1或0
    p(n)表示全部定好了所以只有一种可能了
    对于普遍位置p(i),若i位置选了1，则=p(i+1);
    若i位置选了0，则i+1位置必须选1，否则若选了0左边就没有一个1了，则=p(i+2)
    */
    public static int getMaxNum(int n) {
        if (n < 1)
            return 0;
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        int p1 = 1;
        int p2 = 2;
        int p = 3;
        for(int i = 3; i <= n; i++) {
            p = (p1+p2) % mod;
            p1 = p2;
            p2 = p;
        }
        return p;
    }
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int mod = (int) Math.pow(2, 29);
        int a = 0, b = 1;
        for(int i=0; i<n; i++){
            int c = (a + b) % mod;
            a = b;
            b = c;
        }
        System.out.println(b % mod);
    }
}