Description：

求一个数 $n$ 划分成斐波那契数的方案数之和，要求一个方案中不含有相同数字。

$1\le n \le 10^{18}$

Solution：

$\text{long long}$ 范围内斐波那契数只有 $91$ 个，而又不能有相同的，所以感觉方案会很少，实际也真的很少，于是设 $f[i][j]$ 表示数 $i$ 被分解为 $f_1\sim f_j$ 的方案数，转移时先在前缀和中二分出大于等于 $i$ 的最小的数作为左边界， $j$ 作为右边界，枚举所有这之间的数转移，加一个 $\text{map}$ 记忆化就行了。

Code​：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

typedef long long ll;

ll n;

ll fib[95],sum[95];

map<pair<ll,int>,ll> f;

ll dp(ll n,int m)

{

	if(n == 0)return 1;

	if(n == 1 && m != 1 && m != 2)return 1;

	if(f.find(make_pair(n,m)) != f.end())return f[make_pair(n,m)];

	int p = lower_bound(sum + 1,sum + 91,n) - sum;

	ll res = 0;

	int maxborder = min((int)(upper_bound(fib + 1,fib + 1 + 91,n) - fib - 1),m);

	for(int i = p;i <= maxborder;++i)

	{

		res += dp(n - fib[i],i - 1);

	}

	return (f[make_pair(n,m)] = res);

}

int main()

{

	scanf("%lld",&n);

	fib[0] = fib[1] = sum[1] = 1;

	for(int i = 2;i <= 91;++i)fib[i] = fib[i - 1] + fib[i - 2];

	for(int i = 2;i <= 89;++i)sum[i] = sum[i - 1] + fib[i];

	sum[90] = sum[91] = 0x3f3f3f3f3f3f3f3f;

	cout << dp(n,90) << endl;

	return 0;

}