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

分析

注意到, 如果每个字符串都生成并且计算逆序对

暴力的算法时间复杂度是无法通过

必须要递推观察性质

定义为中逆序对的数量, 表示中的数量, 表示中的数量

由下面转移过来

代码实现

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10, MOD = 1e9 + 7;

LL f[N], z[N], o[N];

void init() {
    z[1] = 1;
    o[2] = 1;
    for (int i = 3; i < N; ++i) {
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
        f[i] = (f[i] + o[i - 2] * z[i - 1] % MOD) % MOD;
        z[i] = (z[i - 1] + z[i - 2]) % MOD;
        o[i] = (o[i - 1] + o[i - 2]) % MOD;
    }
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}