自动搬运

查看原文

来自洛谷，原作者为

	CJR_Rain 666这个入是桂

搬运于2025-08-24 21:17:56，当前版本为作者最后更新于2025-03-09 21:47:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：预处理 $n$ 以内所有不重复的斐波那契数，然后进行 DFS 枚举所有取或不取的可能。

代码：

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;

int dfs(int search, long long cnt) {
    
    if(cnt == 0) {
        
        return 1;
    }
    
    int res = 0;
    
    for(int i = search; i < fib.size(); ++i) {
        
        if(cnt - fib[i] < 0) {
            
            return res;
        }
        
        res += dfs(i + 1, cnt - fib[i]);//不降原则保证选数不重复
    }
    
    return res;
}

signed main() {
    
    IS;
    OS;
    
    long long n;
    cin >> n;
    
    fib.push_back(1);
    fib.push_back(2);
    
    while(fib.back() <= n) {
        
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }
    
    fib.pop_back();
    
    cout << dfs(0, n);
    
    return 0;
}

然而 $10^{12}$ 内不重复的斐波那契数有 $58$ 个，上述代码又是 $O(2^n)$ 级别的时间复杂度，绝对 TLE 。

所以我们需要剪枝

剪枝1：设数列 $k$ 包含 $n$ 以内所有不重复的斐波那契数，然后定义一个变量 $sum=\sum{k}$，在 DFS 搜到 $k$ 中第 $i$ 个数时，$sum=sum-k_i$，代表搜完这个数后 $k$ 中还能搜的数之和。那么设 $t$ 等于已经取的数之和，如果 $n-t>sum$，就可以直接剪枝掉了。

得出代码:

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;//对应k
long long sum_fib = 0;//对应sum

int dfs(int search, long long sum) {//这里跟文中讲得不一样，参数sum = n - t
    
    if(sum <= 0 || sum_fib < sum || search >= fib.size()) {//剪枝1
        
        return sum == 0 ? 1 : 0;
    }
    
    sum_fib -= fib[search];
    int res = dfs(search + 1, sum - fib[search]) + dfs(search + 1, sum);
    sum_fib += fib[search];//利用回溯实现
    
    return res;
}

signed main() {
    
    IS;
    OS;
    
    long long n;
    cin >> n;
    
    fib.push_back(1);
    fib.push_back(2);
    
    while(fib.back() <= n) {
        
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }
    
    fib.pop_back();
    
    sum_fib = accumulate(fib.begin(), fib.end(), 0ll);

    cout << dfs(0, n);

    return 0;
}

交上去一看，还是 TLE ，为什么？因为 $k$ 是单调递增且增速极快的，我们又是从 $k_1$ 开始一个一个搜，就使得在搜 $k$ 中的前几个数时，$sum$ 相对下降得太慢且 $t$ 相对上升得太慢。这样一来，剪枝形同虚设。

我们可以发现，现在 TLE 的原因是 $k$ 单调递增且增速极快，于是提出剪枝2：将 $k$ 反转，使得 $k$ 的性质变成单调递减且降速极快，并且由于没有改动 $k$ 内元素，答案不变。

得出AC代码:

#include <bits/stdc++.h>

#define IS std::cin.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define OS std::cout.tie(nullptr) -> std::ios::sync_with_stdio(false)
#define srnd srand((unsigned int)time(0))
#define rnd rand()
#define save(x) std::fixed << std::setprecision(x)
#define set_0(x) memset(x, 0, sizeof(x))
#define set_false(x) memset(x, false, sizeof(x))
#define set_true(x) memset(x, true, sizeof(x))
#define set_nega1(x) memset(x, -1, sizeof(x))
#define set_Iinf(x) memset(x, 0x7f, sizeof(x))
#define set_Finf(x) memset(x, 7e4, sizeof(x));
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
#define low_bit(x) (x & (-x))
#define __DEBUG__ puts("DEBUG")

using namespace std;

vector <long long> fib;//对应k
long long sum_fib = 0;//对应sum

int dfs(int search, long long sum) {//这里跟文中讲得不一样，参数sum = n - t
    
    if(sum <= 0 || sum_fib < sum || search >= fib.size()) {//剪枝1
        
        return sum == 0 ? 1 : 0;
    }
    
    sum_fib -= fib[search];
    int res = dfs(search + 1, sum - fib[search]) + dfs(search + 1, sum);
    sum_fib += fib[search];//利用回溯实现
    
    return res;
}

signed main() {
    
    IS;
    OS;
    
    long long n;
    cin >> n;
    
    fib.push_back(1);
    fib.push_back(2);
    
    while(fib.back() <= n) {
        
        fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    }
    
    fib.pop_back();
    
    sum_fib = accumulate(fib.begin(), fib.end(), 0ll);
    reverse(fib.begin(), fib.end());//剪枝2
    
    cout << dfs(0, n);

    return 0;
}