题解 | #斐波那契字符串#

斐波那契字符串

https://www.nowcoder.com/practice/704ed5d1c4a34227a85e07ff80025351

题目链接

斐波那契字符串

题目描述

一个由 '0' 和 '1' 构成的斐波那契字符串 $S_n$ 定义如下：

$S_1 = \text{"0"}$
$S_2 = \text{"1"}$
$S_n = S_{n-2} + S_{n-1}$ （"+" 表示字符串拼接）

求 $S_n$ 中逆序对（即子序列 "10"）的数量，答案对 $10^9 + 7$ 取模。

解题思路

本题要求计算特定规则生成的斐波那契字符串 $S_n$ 中 "10" 子序列的数量。由于 $n$ 的值可能很大，我们无法直接构造字符串，必须通过递推关系来解决。

令 $dp[n]$ 表示 $S_n$ 中 "10" 子序列的数量。令 $zeros[n]$ 表示 $S_n$ 中字符 '0' 的数量。令 $ones[n]$ 表示 $S_n$ 中字符 '1' 的数量。

根据定义 $S_n = S_{n-2} + S_{n-1}$ ，我们可以分析 $S_n$ 中逆序对的来源：

来自 $S_{n-2}$ 内部的逆序对：这部分的数量是 $dp[n-2]$ 。
来自 $S_{n-1}$ 内部的逆序对：这部分的数量是 $dp[n-1]$ 。
跨越拼接点的逆序对：即 '1' 来自前面的 $S_{n-2}$ ，'0' 来自后面的 $S_{n-1}$ 。
- $S_{n-2}$ 中 '1' 的数量是 $ones[n-2]$ 。
- $S_{n-1}$ 中 '0' 的数量是 $zeros[n-1]$ 。
- 因此，跨越拼接点产生的逆序对数量为 $ones[n-2] \cdot zeros[n-1]$ 。

综合以上三点，我们可以得到 $dp[n]$ 的递推公式： $dp[n] = dp[n-2] + dp[n-1] + ones[n-2] \cdot zeros[n-1]$

zeros 和 ones 的数量也遵循斐波那契递推： $zeros[n] = zeros[n-2] + zeros[n-1]$ $ones[n] = ones[n-2] + ones[n-1]$

初始条件：

$S_1 = \text{"0"}$ : $zeros[1]=1, ones[1]=0, dp[1]=0$
$S_2 = \text{"1"}$ : $zeros[2]=0, ones[2]=1, dp[2]=0$

性能优化 题目给出的数据范围是 $T$ (测试数据组数) 和 $N$ 均可达 $10^5$ 。如果对每组查询都进行一次 $O(N)$ 的递推，总时间复杂度将是 $O(T \cdot N)$ ，会超时。

正确的做法是预处理。由于 $N$ 的最大值是固定的（ $10^5$ ），我们可以先一次性计算出所有 $n$ 从 $1$ 到 $10^5$ 的答案并存储起来。对于之后的每次查询，直接以 $O(1)$ 的时间复杂度从数组中读取结果即可。这样，总的时间复杂度就优化为 $O(\text{max_N} + T)$ 。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 100001;
vector<long long> dp(MAXN, 0);

// 预处理函数
void precompute() {
    vector<long long> zeros(MAXN, 0);
    vector<long long> ones(MAXN, 0);

    // 初始化
    zeros[1] = 1;
    ones[2] = 1;

    for (int i = 3; i < MAXN; ++i) {
        zeros[i] = (zeros[i - 2] + zeros[i - 1]) % MOD;
        ones[i] = (ones[i - 2] + ones[i - 1]) % MOD;
        long long cross_inversions = (ones[i - 2] * zeros[i - 1]) % MOD;
        dp[i] = (dp[i - 2] + dp[i - 1] + cross_inversions) % MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    cout << dp[n] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute(); // 在处理查询前进行预处理
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final int MAXN = 100001;
    private static long[] dp = new long[MAXN];

    // 预处理
    private static void precompute() {
        long[] zeros = new long[MAXN];
        long[] ones = new long[MAXN];

        if (MAXN > 1) zeros[1] = 1;
        if (MAXN > 2) ones[2] = 1;

        for (int i = 3; i < MAXN; i++) {
            zeros[i] = (zeros[i - 2] + zeros[i - 1]) % MOD;
            ones[i] = (ones[i - 2] + ones[i - 1]) % MOD;
            long crossInversions = (ones[i - 2] * zeros[i - 1]) % MOD;
            dp[i] = (dp[i - 2] + dp[i - 1] + crossInversions) % MOD;
        }
    }

    public static void main(String[] args) {
        precompute(); // 在处理查询前进行预处理
        
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(dp[n]);
        }
    }
}

# 注意：本代码严格遵循了用户的编写要求，
# 使用 input() 而非 sys.stdin.readline。
# 在牛客网等判题平台上，对于大数据量的输入，这可能会导致超时。

MOD = 10**9 + 7
MAXN = 100001
dp = [0] * MAXN

def precompute():
    """
    预处理计算所有n的答案
    """
    global dp
    zeros = [0] * MAXN
    ones = [0] * MAXN

    # 初始化
    if MAXN > 1:
        zeros[1] = 1
    if MAXN > 2:
        ones[2] = 1

    for i in range(3, MAXN):
        # 关键修正：在每一步都进行取模，避免大整数运算
        zeros[i] = (zeros[i-2] + zeros[i-1]) % MOD
        ones[i] = (ones[i-2] + ones[i-1]) % MOD
        cross_inversions = (ones[i-2] * zeros[i-1]) % MOD
        dp[i] = (dp[i-2] + dp[i-1] + cross_inversions) % MOD

def main():
    precompute() # 在处理查询前进行预处理
    
    t = int(input())
    for _ in range(t):
        n = int(input())
        print(dp[n])

if __name__ == "__main__":
    main()