发现斐波那契数列增长极快，不到 \(100\) 项就超过了 \(10^{18}\)，搜索树也极为稀疏，可以考虑搜索。
爆搜肯定会超时，考虑优化：
-
可行性剪枝。
-
记忆化，去除重复的计算。
-
改变搜索的顺序，因为先考虑小元素的话，会有较多的无用的搜索，且小元素较灵活，更容易凑到 \(x\)，故可以从大到小的考虑。
加上这三个优化即可通过此题。
时间复杂度：\(\mathcal{O}\)（可过）
const int N = 100, mod = 998244353;
const ll INF = 1e18;
int n, q;
ll a[N], sum[N];
map<ll, ll> dp[N];
ll dfs(ll x, int cur) {
if (x < 0 || x > sum[cur]) return 0;
if (!cur || !x) return (x == 0);
if (dp[cur].count(x)) return dp[cur][x];
return dp[cur][x] = dfs(x - a[cur], cur - 1) + dfs(x, cur - 1);
}
int main() {
n = 1, a[0] = a[1] = 1;
int m = n;
while (a[m] <= INF) {
a[++m] = 0;
a[m] = a[m - 1] + a[m - 2];
}
n = m - 1;
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
ll x;
cin >> x;
cout << dfs(x, n) << endl;
return 0;
}