简要题意：
设 \(f\) 表示斐波那契数列。给定一个 \(n\) ，求将 \(n\) 分解为 \(f\) 中若干个 不同 的数的和的方案数。
\(n \leq 10^{18}\). 时间限制 \(0.5s\).
这题想给大家分享一个能简单过掉的办法。
先把 \(f\) 写出来：
\[\begin{cases} f_n = 1 \space \space \space\space \space \space\space \space \space\space \space \space\space \space \space\space \space \space\space \space (n \leq 2) \\ f_n = f_{n-1} + f_{n-2} \space \space \space (n > 2) \\ \end{cases}\]写一个小程序验证一下，你就会发现，\(f_{88} = 1100087778366101931\) 已经超过了 \(10^{18}\)！
所以实际参与分解的只可能是 \(f_1 - f_{87}\).
注意到有 \(30 \%\) 的数据，\(n \leq 256\)，肯定是直接爆搜 \(f\) 取和不取。但实际上，\(n \leq 10^{18}\) 又为什么不能？
考虑暴力。
以 \((x,p)\) 作为一个状态，表示现在在决策 \(f_x\) 取或不取，和为 \(p\).
暴力考虑 \(f_x\) 取或不取。
加几个剪枝。我们可以取 \(s\) 作为 \(f\) 的前缀和，那么如果 \(p \geq s_x\)，可以直接得出答案，防止连续不选太多导致大量冗余搜索。
于是我们可以得到第一份代码。
（注意：题目里有个细节，取的是 \(f\) 中不同的数，也就是不能取两个 \(1\)，这点需要稍微弄一下）
Link.
尽管本机对于一些极限数据需要跑到 \(0.55s\) 左右，但在洛谷的评测机之下，毫无疑问，这通过了。
我们希望有一种更优的方法。
我们会发现，对于 \((x,p)\) 状态的个数其实是极为有限的。如果你用 map 计数的话，会发现即使对于 \(n = 10^{18}\) 看起来极为复杂的这一种情况，其实状态个数也没有超过 \(250\).
于是我们自然而然地想到了：记忆化搜索。
在暴力的基础上加一个 map，对于冗余的状态直接跳过。
时间复杂度：\(\mathcal{O}(\texttt{wys})\).
#include <bits/stdc++.h>
using namespace std;
const int N = 88;
typedef long long ll;
ll f[N],s[N],n;
map<pair<ll,ll>,ll> q;
inline ll dfs(register ll x , register ll p) {
if(q[make_pair(x,p)]) return q[make_pair(x,p)];
if(!x) return 0;
if(!p) return 1;
if(p > s[x]) return 0;
if(p == s[x]) return 1;
ll ans = 0;
if(p >= f[x]) ans += dfs(x - 1 , p - f[x]);
ans += dfs(x - 1 , p);
return q[make_pair(x,p)] = ans;
}
int main() {
f[0] = f[1] = 1;
s[0] = 0 , s[1] = 1;
for(int i = 2; i < N; i++) {
f[i] = f[i - 1] + f[i - 2];
s[i] = s[i - 1] + f[i];
}
scanf("%lld",&n);
printf("%lld\n",dfs(86,n));
return 0;
}