被齐肯多夫定理骗了.
本来不知道怎么用不连续的斐波那契数字去表示一个数字,结果查了一下发现直接贪心表示即可,唐完了.

那么设feb(n)是不大于n的最大的斐波那契数列,能二分查出来.

然后边界自己卡一下就可以了.
f的式子前半段可以记忆化,后半段直接递归,算上set查找大概log^2级别.

Vibe Coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

static long long F[100];
unordered_map<long long, long long> dp;

// S(n) = sum_{i=1..n} z(i)
long long S(long long n) {
    if (n <= 0) return 0;
    if (dp.count(n)) return dp[n];

    // 找到最大 Fibonacci F[k] ≤ n
    int k = upper_bound(F, F + 90, n) - F - 1;

    long long res = S(F[k] - 1) + S(n - F[k]) + (n - F[k] + 1);
    return dp[n] = res;
}

int main() {
    // 构造 Fibonacci 数列
    F[0] = 1;  // 按题意：1, 2, 3, 5...
    F[1] = 2;
    for (int i = 2; i < 90; i++) {
        F[i] = F[i - 1] + F[i - 2];
        if (F[i] > (long long)1e18) break;
    }

    long long n = (long long)1e17 - 1; // 题目为 0 < n < 10^17 求 ∑z(n)

    cout << S(n) << endl;
    return 0;
}