B4219题解

洛谷同文链接

B4219 [常州市程序设计小能手 2023] 数学作业 题解

题目传送门

思路

先输入 $n$，将小于等于 $n$ 的所有斐波那契数提前初始化好，存在数组中。也可以提前用打表处理好。然后用 DFS 对于每一个斐波那契数进行选或不选的搜索即可。

void dfs(int i,int sum){
    if(sum+a[i]==n){
        ans++;
        break;
    }
    dfs(i+1,sum);
    dfs(i+1,sum+a[i]);
}

但是，观察一下数据范围：数据范围是 $n\le10^{12}$，而小于等于 $10^{12}$ 的斐波那契数共有大约 $58$ 个，但是我们的算法复杂度为 $O(2^n)$，显然直接就 TLE 了。

于是我们就得想一个优化方法。

优化

使用前缀和优化

我们可以创建前缀和数组 $h$ 使 $h_i$ 表示数列 $f$ 从 $f_0$ 到 $f_{i-1}$的和，若当前选择的斐波那契数和 $s$ 加上后面所有斐波那契数的和还是小于 $n$，则直接退出搜索。

  if(i>=m){
	continue;
}//我这里是模拟递归

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct node{
	int i;
	ll s;
};
int main(){
	ll n;
	cin>>n;
	vector<ll> fib;
	if(n>=1){
		fib.push_back(1);
	}
	if(n>=2){
		fib.push_back(2);
		ll a=1,b=2;
		while(1){
			ll c=a+b;
			if(c>n) break;
			fib.push_back(c);//计算数列
			a=b;
			b=c;
		}
	}
	reverse(fib.begin(),fib.end());//反转数列

	int m=fib.size();

	if(m==0){//特判
		if(n==0) cout<<1;
		else cout<<0;
		return 0;
	}
	vector<ll> prefix(m+1,0);//前缀和数组
	for(int i=m-1;i>=0;i--){
		prefix[i]=fib[i]+prefix[i+1];//计算前缀和
	}

	stack<node> st;

	st.push({0,n});//初始化栈

	ll ans=0;

	while(!st.empty()){
		node temp=st.top();
		st.pop();
		int i=temp.i;
		ll s=temp.s;

		if(s==0){//如果s=0，答案+1
			ans++;
			continue;
		}
		if(i>=m){//如果i>=m，跳过
			continue;
		}

		if(fib[i]>s){//如果当前数大于s，将当前数入栈
			st.push({i+1,s});
		}
		else{
			if((i+1<m)?prefix[i+1]<s:0<s){//如果当前数小于s，将当前数入栈，将当前数的下一个数入栈
				st.push({i+1,s-fib[i]});
			}
			else{//如果当前数小于s，将当前数入栈，将当前数的下一个数入栈
				st.push({i+1,s});
				st.push({i+2,s-fib[i]});
			}
		}
	}
	cout<<ans;
    return 0;
}