题解：P6361 [CEOI 2018] Fibonacci representations

paper_ · 2026-10-20 15:16:57 · 题解

某神秘模拟赛 T4，将凶区冈创飞。

手玩一下，发现如果将 F_i 拆成 F_{i-1} 与 F_{i-2} 后 F_{i-1} 就一定不能拆了，否则必然会有重合，因此一个 F_i 最后拆出来的 Fibonacci 进制表示一定是一个 00000000001\to11010101010 的样子。

对于一个正整数，我们可以将其拆成 Fibonacci 数列中不相邻的若干个数的和，根据上面的结论，我们也容易推出如果原数能拆成 F_{s_1}+F_{s_2}+\dots+F_{s_k} ({s_i}<s_{i+1}-1) 那么 F_{s_{i+1}} 扩展成的 1101010 段一定不能跨过 F_{s_i}。

你甚至可以发现 F_{s_{i+1}} 能扩展的长度是否变化都只跟 F_{s_i} 是否扩展有关（F_{s_i} 扩展会使 s_i 这个位置变成 0，多出一个空位），因此设 f_{i,0/1} 表示考虑前 i 项，且 F_{s_i} 不拆／拆开的方案数，就可以写出转移，并用矩阵维护。

现在的难点是如何快速维护前缀和的 Fibonacci 拆分，假设当前插入的是 F_u。

• 若 u、u+1 与 u-1 当前都是 0，直接将 u 这个位置改为 1 即可。
• 如果 u+1 或 u-1 当前为 1，进位过程就是将 u 向右的极长 0101 段缩成一个 1。
• 若 u 本就是 1，只需要将当前插入的 F_u 先完整拆开，此时刚好可以将 u 前的极长 0101 段的多余空位填满，进位后刚好就相当于区间平移了一下，如果 0101 段的左端点为 F_1 或 F_2 需要特殊考虑一下。

可以直接用平衡树大力维护所有 0101 段，由于每个段的矩阵只依赖段长以及它与前段的距离，修改一个段时，只需重算它自己和后继的矩阵。巧妙一点的方法是先使用 set/map 模拟整个过程，将需要用到的下标离散化后在第二遍模拟时使用线段树维护，代码不压行甚至只有 2.5k，轻取 QOJ 最短解+最优解，但是 luogu 上肘不赢 rizynvu 大哥是怎么回事呢 qwq。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, mod = 1e9 + 7;
typedef long long ll;
int n, op, m, a[N];
vector<int> b;
map<int, int> s;
struct MAT {
    ll a, b, c, d;
    MAT operator * (const MAT &t) const {
        return {
            ((a * t.a + b * t.c) % mod),
            ((a * t.b + b * t.d) % mod),
            ((c * t.a + d * t.c) % mod),
            ((c * t.b + d * t.d) % mod)
        };
    }
};
const MAT I = {1, 0, 0, 1};
vector<MAT> t;
MAT get(int d, int k) {
    int x = (d - 1) / 2, y = d / 2;
    return {(int)(((ll)x * (k - 1) + 1) % mod), x,
        (int)(((ll)y * (k - 1) + 1) % mod), y};
}
void upd(int x, MAT v) {
    if (!op) { b.push_back(x); return; }
    x = lower_bound(b.begin(), b.end(), x) - b.begin() + m;
    t[x] = v;
    for (x >>= 1; x; x >>= 1) t[x] = t[x << 1] * t[x << 1 | 1];
}
void calc(map<int, int>::iterator it) {
    if (it == s.end()) return;
    int l = it->first, r = it->second, p = 0;
    if (it != s.begin()) p = prev(it)->second;
    upd(l, get(l - p, (r - l) / 2 + 1));
}
void change(int l, int r) {
    if (l > r) return;
    auto it = s.lower_bound(l);
    if (it != s.end() && it->first == l) upd(l, I), it = s.erase(it);
    else it = s.insert({l, r}).first, calc(it ++);
    calc(it);
}
void ins(int x) {
    auto it = s.upper_bound(x + 1);
    if (it != s.begin() && prev(it)->second >= x - 1) {
        it --;
        int l = it->first, r = it->second;
        change(l, r);
        if (x - l & 1) {
            change(l, min(x - 1, r - 2));
            ins(max(x + 1, r + 1));
        }
        else {
            change(l + 1, x - 1);
            if (l > 1) ins(max(1, l - 2));
            ins(r + 1);
        }
    }
    else {
        int l = x, r = x;
        if (it != s.begin() && prev(it)->second == x - 2)
            l = prev(it)->first, change(l, x - 2);
        if (it != s.end() && it->first == x + 2)
            r = it->second, change(x + 2, r);
        change(l, r);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], ins(a[i]);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (m = 1; m < (int)b.size(); m <<= 1) ;
    t.assign(m << 1, I);
    s.clear(), op = 1;
    for (int i = 1; i <= n; i ++ ) {
        ins(a[i]);
        cout << (t[1].a + t[1].b) % mod << '\n';
    }
    return 0;
}

:::