A23493. 数学作业今天小X的数学老师带领大家学习了斐波那契序列：斐波那契序列指的是这样一个数列：1、2、3、5、8、13、21、34。从第3个数开始，每个数都是前两个数的和，比如8=3+5，34=13+21。数列里的数叫做斐波那契数。一个数n的斐波那契表示是指把n写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如14有三种斐波那契表示：14=1+13，14=1+5+8，14=1+…
填空题
较难
知识点
题目描述
数学作业
今天小X的数学老师带领大家学习了斐波那契序列：
斐波那契序列指的是这样一个数列：1、2、3、5、8、13、21、34。从第3个数开始，每个数都是前两个数的和，比如8=3+5，34=13+21。数列里的数叫做斐波那契数。
一个数n的斐波那契表示是指把n写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如14有三种斐波那契表示：14=1+13，14=1+5+8，14=1+2+3+8。数学老师给小X留下了一个数学作业，她告诉小X一个正整数n，想让小X算出n有多少种不同的斐波那契表示。
小X请你帮助他完成他的数学作业。
输入
第一行为一个正整数n。
输出
输出一行一个整数表示答案。
样例输入1
14样例输入2
1110样例输入3
1000000000000样例输出1
3样例输出2
21样例输出3
283392数据范围
对于测试点1-5：1<=n<=10^4
对于测试点6-8：1<=n<=10^9
对于测试点9-10：1<=n<=10^12
参考答案
#include <iostream>
#include <vector>
using namespace std;
vector<long long> fib;
// 预处理斐波那契数列（1,2,3,5,...）
void init_fib(long long n) {
fib.push_back(1);
fib.push_back(2);
while (true) {
long long next = fib.back() + fib[fib.size() - 2];
if (next > n) break;
fib.push_back(next);
}
}
// 递归计算表示数
long long count_ways(long long n, int idx) {
if (n == 0) return 1;
if (idx < 0 || fib[idx] > n) return 0;
// 不选当前fib[idx]
long long res = count_ways(n, idx - 1);
// 选当前fib[idx]（跳过前一个，避免重复）
res += count_ways(n - fib[idx], idx - 2);
return res;
}
int main() {
long long n;
cin >> n;
init_fib(n);
cout << count_ways(n, fib.size() - 1) << endl;
return 0;
}
上一题
下一题