题目描述

今天小 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 请你帮助他完成他的数学作业。

解题思路

我们发现，在$10^{12}$内的斐波那契数不超过60个，但是$2^{60}$还是过大。

怎么办？

剪枝!

如果一个斐波那契数大于原来的$n$，那么这个数一定取不到，也就不用进入dfs了。

如果一个斐波那契数前面的斐波那契数加起来（也就是前缀和）还小于当前的$n$（指选完比它大的数后的剩下的$n$），那这个方案就一定不行了，所以直接$return$.

这样看起来时间复杂度是一样的，但是实际上会跑得非常快，经过chufuzhe巨佬的测试，完全能过。

代码（by chufuzhe）

抄代码的人，我们一般叫他PuBliC

#include<bits/stdc++.h>
using namespace std;
namespace io {
    char buf[1 << 21], *p1 = buf, *p2 = buf, buf1[1 << 21];
    inline char gc() {
        if (p1 != p2)
            return *p1++;
        p1 = buf;
        p2 = p1 + fread(buf, 1, 1 << 21, stdin);
        return p1 == p2 ? EOF : *p1++;
    }
    #define G gc

    #ifndef ONLINE_JUDGE
    #undef G
    #define G getchar
    #endif

    template <class I>
    inline void read(I &cn) {
        char c; int sig = 1;
        while(!isdigit(c = G())) if(c == '-') sig = 0;
        if(sig) {cn = c-48; while(isdigit(c = G())) cn = (cn<<3)+(cn<<1)+(c-48); }
        else    {cn = 48-c; while(isdigit(c = G())) cn = (cn<<3)+(cn<<1)+(48-c); }
    }
    inline void write(int n) {
    	if(n < 0) {
    		putchar('-');
    		write(-n);
    		return ;
		}
		if(n < 10) {
            putchar(n % 10 + '0');
            return ;
        }
        write(n / 10);
        putchar(n % 10 + '0');
    }
}
using namespace io;
long long a[100], mx[100];
int ans = 0;
void dfs(long long n, int dep) {
	if(n == 0) { ans++; return ; }
	if(dep == 0) return ;
	if(mx[dep] < n) return ;
	if(a[dep] <= n) dfs(n - a[dep], dep - 1);
	dfs(n, dep - 1);
}
int main() {
	long long n;
	cin >> n;
	a[1] = 1; a[2] = 2;
	mx[1] = 1; mx[2] = 3;
	for(int i = 3; ; i++) {
		a[i] = a[i - 1] + a[i - 2];
		mx[i] = mx[i - 1] + a[i];
		if(a[i] > n) {
			dfs(n, i - 1);
			cout << ans << endl;
			return 0;
		}
	}
	return 0;
}

//Written By : TZR087
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[60],s[60],ans,n,cnt=2;
void work(ll dep,ll rest){
	if(rest==0){
		ans++;
		return ;
	}
	if(dep[s]<rest)return ;
	work(dep-1,rest);
	if(dep[a]<=rest)work(dep-1,rest-dep[a]);
}
int main(){
	cin>>n;
	1[a]=1,2[a]=2,1[s]=1,2[s]=3;
	while(true){
		cnt++;
		cnt[a]=(cnt-1)[a]+(cnt-2)[a];
		cnt[s]=(cnt-1)[s]+cnt[a];
		if(cnt[a]>n)break;
	}
	work(cnt-1,n);
	cout<<ans;
	return 0;
}

CF126D简化版