求一个数表示为几个Fib[]之和的方案数。n<=10^18。

首先发现fib增长的很快。到了89就爆long long了。那么总共就88个数可用。

然后可以利用贪心从大到小得到一种方案。比如25。先从大的fib数开始取。所以25=f[7]+f[3]+f[1]=21+3+1。

用二进制来表示选中的fib数就是：1010001（从小到大）

注意到：因为fib[i]=fib[i-1]+fib[i-2]。所以001和110是等价的。那么我们就可以从第一个推到最后一个每一位可以取1也可以不取1。

如果不取1。那就有cnt/2种取法（cnt为这个1和前面一个1中间的0的个数）。然后乘法原理就行了。

dp的时候只需要枚举1的位置即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long f[89],a[89],n,g[89][2];	int m=0;
int main(){
	cin >> n;
	f[1]=1;	f[2]=2;
	for(int i=3;i<=88;i++)	f[i]=f[i-1]+f[i-2];
	for(int i=88;i>=1;i--)	if(f[i]<=n)	n-=f[i],a[++m]=1LL*i;
	reverse(a+1,a+m+1);
	g[1][1]=1;
	g[1][0]=(a[1]-1)>>1;
	for(int i=2;i<=m;i++){
		g[i][1]=g[i-1][0]+g[i-1][1];
		g[i][0]=((a[i]-a[i-1]-1)>>1)*g[i-1][1]+((a[i]-a[i-1])>>1)*g[i-1][0];
	}cout << g[m][1]+g[m][0] << endl;
	return 0;
}

• 相关文章