这题是旁边同学介绍的，听他说记忆化搜索可以过。。。
不过我还是老老实实的想\(dp\)吧～
先看看数据范围，\(n\leq10^{18}\)相当于\(n \leq fib[86]\)。
以前打\(cf\)的时候做过一个题目，好像证明过任何数都可以用斐波那契数组成。
不过现在忘记证了。。。
但是刚好这个可以派上用场，先假设\(p[i]\)代表组成\(n\)的第\(i\)个斐波那契数的位置。
另外，还有一个性质我们也需要分析出来。
因为\(fib[i]=fib[i-1]+fib[i-2]\)，所以每个斐波那契数都可以有两种选择。
选择分裂，或不分裂。
那么我们令\(f[i][0/1]\)代表枚举到第\(i\)个组成\(n\)的斐波那契数此时的方案数。
0是不分裂，1是分裂。
所以状态这么转移：
\[f[i][0]=f[i-1][0]+f[i-1][1]
\]
\[f[i][1]=(p[i]-p[i-1]-1)/2*f[i-1][0]+(p[i]-p[i-1])/2*f[i-1][1]
\]
为什么呢？
\(f[i][0]\)很显然，不用说。
对于\(f[i][1]\)，第\(i\)位分裂，显然它前面有\(p[i]-p[i-1]>>1\)个方案是\(f[i-1][1]\)(分裂)的。
而前面的\(f[i-1][0]\)如果是不分裂，那么方案\(-1\)。
那么代码(复杂度\(O(86)\))：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a[86]={0,1,2},f[86][2]={};
ll n,p[86]={},cnt;
cin>>n;
for (int i=3;i<=85;++i)
a[i]=a[i-1]+a[i-2];
for (int i=85;i;--i)
if (n>=a[i])
n-=a[i],p[++cnt]=i;
reverse(p+1,p+1+cnt);
f[1][0]=1;f[1][1]=(p[1]-1)/2;
for (int i=2;i<=cnt;++i) {
f[i][0]=f[i-1][1]+f[i-1][0];
f[i][1]=(p[i]-p[i-1]-1)/2*f[i-1][0]+(p[i]-p[i-1])/2*f[i-1][1];
}
cout<<f[cnt][1]+f[cnt][0];
return 0;
}