题目大意

斐波那契数列定义为： [ F_1 = 1,\quad F_2 = 2,\quad F_n = F_{n-1}+F_{n-2}\ (n\ge 3) ] 即：$1, 2, 3, 5, 8, 13, 21, \dots$

定义：
$X(p)$ 表示将正整数 $p$ 表示成不同斐波那契数之和的方案数，不同的斐波那契数 $F_i$ 与 $F_j$ 视为不同元素。
两种表示法不同当且仅当存在一个斐波那契数在一个表示中出现，另一个表示中不出现。

问题：
给定一个序列 $a_1, a_2, \dots, a_n$，令 $p_k = F_{a_1} + F_{a_2} + \dots + F_{a_k}$。
对每个 $k = 1, 2, \dots, n$，输出 $X(p_k) \bmod (10^9+7)$。

$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。

---

思路分析

这是一个计数问题，关键在于理解“不同斐波那契数表示”的性质以及斐波那契数系（Zeckendorf 表示） 的变种。

1. 斐波那契数系与唯一表示

经典结论：任何正整数 $p$ 可以唯一表示成若干个不相邻的斐波那契数 $F_i$ 的和（且不能使用 $F_1$ 和 $F_2$ 同时出现，因为 $F_1=F_2$ 在定义中不同，这里我们按照本题定义 $F_1=1,F_2=2$，可以同时出现）。

但本题中 $X(p)$ 是所有不同斐波那契数的方案，不要求“不相邻”，只要求不同。
例如样例中 $p=5$ 可以是 $F_4=5$，也可以是 $F_2+F_3=2+3$。

我们需要找到一种方法来计算方案数。

---

2. 基本思路：转换为二进制状态

一种常见思路是利用斐波那契数的性质：
$F_i = F_{i-1}+F_{i-2}$ 可以推出 $F_i$ 与 $F_{i-1},F_{i-2}$ 之间的替换关系。

考虑维护 $p_k$ 的一个“最小表示”，即用 Zeckendorf 表示（不相邻表示），然后考虑相邻位的转移来计数。

---

3. 关键性质

设 $p$ 的 Zeckendorf 表示为： [ p = F_{i_1} + F_{i_2} + \dots + F_{i_m},\quad i_1 > i_2 > \dots > i_m,\quad i_j - i_{j+1} \ge 2 ] 这样的表示是唯一的。

我们可以将 $p$ 表示为一个二进制串 $b_1 b_2 \dots b_t$，其中 $b_j=1$ 表示 $F_j$ 被使用，并且满足 $b_j$ 和 $b_{j+1}$ 不能同时为 1（不相邻条件）。

---

4. 动态添加 $F_{a_k}$ 的影响

当我们加入一个新的 $F_{a_k}$ 时，需要将它加到当前 $p_{k-1}$ 的 Zeckendorf 表示中。

核心操作：
令当前 Zeckendorf 表示的二进制串为 $b$（下标从大到小）。加入 $F_x$：

• 如果 $b_x=0$ 且 $b_{x+1}=0$（或 $x$ 是最高位），则直接置 $b_x=1$。
• 否则，$b_x$ 已经有 1，那么使用斐波那契恒等式 $2F_x = F_{x+1}+F_{x-2}$（但注意我们的 $F_1,F_2$ 定义不同，需要小心边界），实际更简单的方法是用： 进位规则：
  如果 $b_x=1$，则 $F_x + F_x = F_{x+1} + F_{x-2}$（当 $x\ge 3$）。
  特别地，$F_1+F_1 = F_2$，$F_2+F_2 = F_3$。

实际上，常用的是 “斐波那契进制”的加法规则： [ 2F_i = F_{i+1} + F_{i-2},\quad i\ge 3 ] [ 2F_2 = F_3 ] [ 2F_1 = F_2 ]

所以加 $F_x$ 到已有 $b_x=1$ 时，相当于：

• 将 $b_x$ 置 0，$b_{x+1}$ 加 1，同时 $b_{x-2}$ 加 1（如果 $x\ge 3$）。
• 这会引发连锁进位，直到 Zeckendorf 条件满足（无相邻 1）。

---

5. 维护方案数

本题难点在于求 $X(p)$ —— 允许相邻的表示法数。

已知 Zeckendorf 表示是唯一的“无相邻1”表示，其他表示可以通过 “11” → “001” 的局部变换得到（即 $F_i+F_{i+1} = F_{i+2}$）。

换句话说，如果当前 Zeckendorf 表示中某段是 ...0110...，我们可以变成 ...1000...（不唯一，因为可以分段变换）。
这其实等价于：将连续的 1 分组，每组长度为 $l$ 的 1 串（不相邻的 1 之间至少隔一个 0）可以独立变换。

---

重要结论（来自本题的经典结论）：
设 Zeckendorf 表示中，将 1 的位置从高到低记为 $i_1,i_2,\dots,i_m$，且 $i_j - i_{j+1} \ge 2$。
则 $X(p)$ 的计算可以转化为： 将每个间隔 $d_j = i_j - i_{j+1}$ 考虑，如果 $d_j$ 是偶数，则中间可以插入一些变换；如果 $d_j$ 是奇数，则变换方式唯一。

具体公式： 令 $g_j = \lfloor \frac{d_j - 1}{2} \rfloor$，则总方案数为： [ X(p) = \prod_{j=1}^{m-1} (g_j + 1) ] 其中 $d_j = i_j - i_{j+1}$，$m$ 是 1 的个数。

---

6. 维护数据结构

我们需要支持：

1. 加 $F_{a_k}$ 到当前表示，并更新 Zeckendorf 二进制串。
2. 维护所有 $d_j$（相邻 1 的间隔）。
3. 动态更新乘积 $\prod (g_j+1)$。

操作 1 可能引起很多位的进位，但注意 $a_i \le 10^9$，所以 $F_{a_i}$ 的指数很大，我们不能直接开数组到 $10^9$。
优化：使用 std::map<int, int> 存储非零的 $b_i$（1 的位置），因为每次操作只会影响 $O(\log a_i)$ 个位置（进位链长度有限）。

---

7. 算法步骤

1. 用 map<int,int> 表示当前二进制串 $b$，键是下标 $i$，值 $b_i \in \{0,1\}$（实际上只会存 1 的位置，0 不存）。
2. 加入 $F_x$：
   • 找到 $x$ 在 map 中的位置：
     • 如果 $b_x=0$，直接置 1。
     • 如果 $b_x=1$，则触发进位：
       置 $b_x=0$，$b_{x+1}$ 加 1，$b_{x-2}$ 加 1（若 $x\ge 3$）。
       注意 $b_{x+1}$ 若原本为 1，则继续进位。
   • 进位过程用 while 循环处理。
3. 维护一个 map<int,int> 存间隔 $d_j$ 的数量（方便更新乘积）。
   • 每次 $b$ 改变时，受影响的是几个相邻的 1 位置，我们只需要更新受影响的间隔。
   • 用模乘逆元更新乘积 $(g_j+1)$。
4. 输出当前乘积。

---

8. 时间复杂度

每次加法操作，进位链长度 $O(\log p)$，而 $p$ 增长很快，但 $a_i$ 到 $10^9$，实际进位链长度也有限（约 $O(\log a_i)$）。
用 map 维护，每次操作 $O(\log n)$ 次 map 操作，总复杂度 $O(n \log a_i \log n)$，可以通过。

---

代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;

int mod_inv(int x) {
    // 费马小定理求逆元，MOD 是质数
    int res = 1, y = MOD - 2;
    while (y) {
        if (y & 1) res = (ll)res * x % MOD;
        x = (ll)x * x % MOD;
        y >>= 1;
    }
    return res;
}

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

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    map<int, int> bits; // 存储 b[i]=1 的位置 i
    map<int, int> gap_count; // 间隔 d_j 的计数（实际存储 g_j = floor((d_j-1)/2)）
    int ans = 1;

    auto update_gap = [&](int pos, int delta) {
        // pos 和 pos+delta 是相邻 1 的位置变化
        // 这里简化，实际需要根据受影响的两个间隔更新
        // 具体实现需要细心处理
    };

    for (int x : a) {
        // 1. 找到 x 所在位置，开始加法进位
        int cur = x;
        while (bits[cur] == 1) {
            bits.erase(cur);
            cur++;
            bits[cur] ^= 1;
            if (bits[cur] == 0) bits.erase(cur);
            if (cur >= 3) {
                int t = cur - 2;
                bits[t] ^= 1;
                if (bits[t] == 0) bits.erase(t);
                if (bits[t] == 1) {
                    cur = t;
                    continue;
                }
            }
            // 更新 gap_count 和 ans
            // 略去细节
        }
        bits[cur] = 1;
        // 更新 gap_count 和 ans
        // 略去细节

        cout << ans << '\n';
    }
    return 0;
}

---

总结

本题的关键在于：

1. 利用斐波那契进制的进位规则来维护 Zeckendorf 表示。
2. 利用公式 $X(p) = \prod_{j=1}^{m-1} \left(\lfloor \frac{d_j - 1}{2} \rfloor + 1\right)$ 计算方案数。
3. 使用 map 动态维护非零位，支持大下标更新。
4. 模逆元维护乘积的动态更新。

最终时间复杂度 $O(n \log a_i \log n)$，空间 $O(n)$。