思路：动态规划

状态定义：

$dp[i][j]$ 表示前 $i$ 个数，第 $i$ 个数为 $j$ 的方案数。

状态转移： $dp[i][0] = dp[i - 1][1]$

$dp[i][1] = dp[i - 1][0] + dp[i - 1][0]$

最后答案为：$dp[n][0] + dp[n][1]$

时间复杂度：$O(n)$

代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // dp[i][0] 表示前 i 个数，第 i 个数为 0 的方案数
    // dp[i][1] 表示前 i 个数，第 i 个数为 1 的方案数
    vector<vector<int>> dp(n + 1, vector<int>(2, 0));
    dp[1][0] = 1;
    dp[1][1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
    }

    cout << (dp[n][0] + dp[n][1]) % MOD << "\n";

    return 0;
}

Python

MOD = int(1e9) + 7

n = int(input())

pre = [1, 1]
cur = [0, 0]

for i in range(2, n + 1):
    cur[0] = pre[1]
    cur[1] = (pre[0] + pre[1]) % MOD
    pre[0], pre[1] = cur[0], cur[1]

result = (pre[0] + pre[1]) % MOD
print(result)

Java

import java.util.Scanner;

public class Main {
    public static final int MOD = 1000000007;

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

        int[][] dp = new int[n + 1][2];
        dp[1][0] = 1;
        dp[1][1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][1];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
        }

        int result = (dp[n][0] + dp[n][1]) % MOD;
        System.out.println(result);
    }
}

题目内容

小红有 $n$ 个数字 $0$ 和 $n$ 个数字 $1$ 。

现在，小红要从这 $2n$ 个数字中选出 $n$ 个数字进行排列。

但是对小红来说，排列中连续出现两个 $0$ 是让他不能接受的。

现在，小红想问你，可以选出多少种不同的排列方式。

输入描述

一行，一个整数 $n(1\leq n\leq 5\times 10^6)$ 表示有 $n$ 个数字 $0$ 和 $n$ 个数字 $1$ 。

输出描述

输出不同排列的方案数，答案对 $10^9 + 7$ 取模。

样例

输入

2

输出

3

说明 00 不符合小红的要求，01, 10, 11 都是符合要求的。共有 $3$ 种。