斐波那契字符串

思路

题目定义了斐波那契字符串：，，（拼接）。要求统计 中的逆序对数量，即满足 且 ， 的 对数，结果对 取模。

显然不能把字符串构造出来暴力数，因为长度是斐波那契级别增长的。我们需要找递推关系。

，所以 的逆序对来自三部分：

  1. 左半部分 内部的逆序对
  2. 右半部分 内部的逆序对
  3. 跨越左右的逆序对：左边的 '1' 和右边的 '0' 配对

所以核心递推式：

$$

其中 和 分别是 中 '1' 和 '0' 的个数，它们也满足斐波那契递推：

用样例验证：

  • ：，。正确！
  • ：，。正确！

由于有多组查询（ 可达 5000， 可达 ），我们预处理所有 的答案，每次 回答即可。

代码

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

const int MOD = 1e9 + 7;
const int MAXN = 100001;

long long f[MAXN], ones[MAXN], zeros_arr[MAXN];

int main(){
    ones[1] = 0; ones[2] = 1;
    zeros_arr[1] = 1; zeros_arr[2] = 0;
    f[1] = 0; f[2] = 0;
    for(int i = 3; i < MAXN; i++){
        ones[i] = (ones[i-1] + ones[i-2]) % MOD;
        zeros_arr[i] = (zeros_arr[i-1] + zeros_arr[i-2]) % MOD;
        f[i] = (f[i-1] + f[i-2] + ones[i-2] % MOD * (zeros_arr[i-1] % MOD)) % MOD;
    }
    int T;
    scanf("%d", &T);
    while(T--){
        int n;
        scanf("%d", &n);
        printf("%lld\n", f[n]);
    }
    return 0;
}

import java.io.*;

public class Main {
    static final long MOD = 1000000007L;
    static final int MAXN = 100001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long[] f = new long[MAXN];
        long[] ones = new long[MAXN];
        long[] zeros = new long[MAXN];

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

        int T = Integer.parseInt(br.readLine().trim());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            sb.append(f[n]).append('\n');
        }
        System.out.print(sb);
    }
}

import sys
input = sys.stdin.readline

MOD = 10**9 + 7
MAXN = 100001

f = [0] * MAXN
ones = [0] * MAXN
zeros = [0] * MAXN

ones[1] = 0; ones[2] = 1
zeros[1] = 1; zeros[2] = 0

for i in range(3, MAXN):
    ones[i] = (ones[i-1] + ones[i-2]) % MOD
    zeros[i] = (zeros[i-1] + zeros[i-2]) % MOD
    f[i] = (f[i-1] + f[i-2] + ones[i-2] * zeros[i-1]) % MOD

T = int(input())
out = []
for _ in range(T):
    n = int(input())
    out.append(str(f[n]))
print('\n'.join(out))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const MOD = 1000000007n;
    const MAXN = 100001;
    const f = new Array(MAXN).fill(0n);
    const ones = new Array(MAXN).fill(0n);
    const zeros = new Array(MAXN).fill(0n);

    ones[1] = 0n; ones[2] = 1n;
    zeros[1] = 1n; zeros[2] = 0n;

    for (let i = 3; i < MAXN; i++) {
        ones[i] = (ones[i-1] + ones[i-2]) % MOD;
        zeros[i] = (zeros[i-1] + zeros[i-2]) % MOD;
        f[i] = (f[i-1] + f[i-2] + ones[i-2] * zeros[i-1]) % MOD;
    }

    let idx = 0;
    const T = parseInt(lines[idx++]);
    const out = [];
    for (let t = 0; t < T; t++) {
        const n = parseInt(lines[idx++]);
        out.push(f[n].toString());
    }
    console.log(out.join('\n'));
});

复杂度

  • 时间复杂度：，其中 是预处理上界， 是查询次数。
  • 空间复杂度：，存储预处理数组。